Sort, Sweep, Mirror: Batch Private Interval Lookup with Logarithmic Cost

Secure multiparty computation often requires table lookups and piecewise polynomial evaluation for efficiency. Hiding both the table and the accessed entry is essential. Existing work on private lookup table (LUT) protocols either incur Ω(mL) computation and communication (Eurocrypt '24), where ℓ is the input bitwidth, m is the output bitwidth, and L = 2 ℓ , or are optimized for small tables (NDSS '25). Realizing O(ℓ log L) communication and O((ℓ + m) log L) computation per query for the first time, we propose a batch private LUT protocol that overcomes these limitations by processing K lookups with O(K log L) secure comparisons. More generally, our approach extends to private interval LUT (ILUT) enabling efficient interval-based lookups in batches. Applications include private machine learning over a large input range, which small LUTs cannot approximate accurately. Notably, it supports inverse-square-root approximation and secure multiplication common in quantized neural networks, where outputs are dependent on the private model weights. Systematic experiments demonstrate that our protocol reduces communication by 10.56-to 1984-fold over the state of the art for private LUTs with tables ranging from 2 16 to 2 24 entries. Moreover, it supports >2 11 lookups per second for a 2 24 -entry table in a local-area network and >2 9 in a wide-area network.

1. Following standard secret sharing semantics, our protocol operates on unsigned integers but can be generalized to accommodate signed integers and floating-point numbers (common in ML applications) by encoding them with two's complement and fixed-point encoding [24], respectively.