Paper 2024/1093

ROTL: Faster Lookup Table Evaluation

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 $\mathsf{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.3\times$ speedup and $10.5 \times$ communication reduction in overall (preprocessing + online) and $21 \times$ speedup and $60 \times$ communication reduction in terms of the online phase. At the heart of $\mathsf{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 $\mathsf{ROTL}$, we design a novel secure comparison protocol; compared with the state-of-the-art (USENIX '22), it achieves a $5\times$ runtime speedup and $2.5\times$ 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^2l)$ to $O(n\log n + nl)$ and shift $O(n\log n)$ computation to the preprocessing phase without introducing communication overhead. As a result, FLUTE+ achieves up to $5\times$ speedup in terms of overall (preprocessing and online) and over $600\times$ 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.