ROTL: Faster Lookup Table Evaluation
Xiaoyang Hou, Jian Liu, Jingyu Li +3 more
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.
Proceedings on Privacy Enhancing Technologies•Apr 1, 2026•0 citations