ROTL: Faster Lookup Table Evaluation
Authors: Xiaoyang Hou (The State Key Laboratory of Blockchain and Data Security, Zhejiang University.), Jian Liu (The State Key Laboratory of Blockchain and Data Security, Zhejiang University; Hangzhou High-Tech Zone (Binjiang) Blockchain and Data Security Research Institute.), Jingyu Li (The State Key Laboratory of Blockchain and Data Security, Zhejiang University.), Jiawen Zhang (The State Key Laboratory of Blockchain and Data Security, Zhejiang University.), Kui Ren (The State Key Laboratory of Blockchain and Data Security, Zhejiang University; Hangzhou High-Tech Zone (Binjiang) Blockchain and Data Security Research Institute.), Chun Chen (The State Key Laboratory of Blockchain and Data Security, Zhejiang University; Hangzhou High-Tech Zone (Binjiang) Blockchain and Data Security Research Institute.)
Volume: 2026
Issue: 2
Pages: 499–516
DOI: https://doi.org/10.56553/popets-2026-0058
Abstract: Lookup table (LUT) is an important cryptography primitive, widely used in secure applications such as private set intersection, boolean circuit evaluation, and privacy-preserving machine learning. However, existing LUT constructions suffer from either high overhead or limited functionality.
In this paper, we propose ROTL, a secure two-party protocol for arithmetic LUT evaluation. Compared with SP-LUT (the state-of-the-art arithmetic LUT presented at NDSS '17), it achieves up to 3.3x speedup and 10.5x communication reduction in overall (preprocessing + online) and 21x speedup and 60x communication reduction in terms of the online phase.
At the heart of ROTL is a novel protocol for secret-sharing rotation, which allows two parties to generate additive secret shares of the rotated table without revealing the rotation offset. We believe this protocol is of independent interest. Based on ROTL, we design a novel secure comparison protocol; compared with the state-of-the-art (USENIX '22), it achieves a 5x runtime speedup and 2.5x communication reduction in the online performance.
To support boolean secret sharing, we further provide an optimization (named FLUTE+) for FLUTE (the state-of-the-art boolean LUT presented at Oakland '23). For a boolean LUT with table size n and elements bit-width l, we reduce FLUTE's computation complexity from O(n^2 l) to O(n log n + n l) and shift O(n log n) computation to the preprocessing phase without introducing communication overhead. As a result, FLUTE+ achieves up to 5x speedup in terms of overall (preprocessing and online) and over 600x speedup in terms of the online phase compared with FLUTE. The communication cost of FLUTE+ is exactly the same as FLUTE's in both the preprocessing phase and the online phase.
Keywords: privacy-preserving protocols, two-party secure computation
Copyright in PoPETs articles are held by their authors. This article is published under a Creative Commons Attribution 4.0 license.
