Paper 2025/2109

Secure Lookup Tables: Faster, Leaner, and More General

Pengfei Zhu, Tsinghua University

Yun Li, Ant Group

Zhanpeng Guo, Ant Group

Jingyu Li, Ant Group

Yuncong Hu, Shanghai Jiao Tong University

Zhicong Huang, Ant Group

Cheng Hong, Ant Group

Abstract

Secure lookup table (LUT) protocols allow retrieving values from a table at secret indices, and have become a promising approach for the secure evaluation of non-linear functions. Most existing LUT protocols target the two-party setting, where the best protocols achieve a communication cost of $O(N)$ for a table of size $N$. MAESTRO (Morita et al., USENIX Security 2025) represents the state-of-the-art LUT protocol for AES in the three-party honest-majority setting, with a communication cost of $O(N^{1/2})$; malicious security is achieved with distributed zero-knowledge proofs. However, it only supports single-input tables over characteristic-2 fields $\mathbb{F}_{2^k}$ and lacks support for multi-input tables over rings $\mathbb{Z}_{2^k}$, which are more widely used in modern computation. Moreover, the $O(N^{1/2})$ cost remains expensive for large-scale applications; their efficient distributed zero-knowledge proofs are specialized for AES and cannot be easily applied to $\mathbb{Z}_{2^k}$. In this work, we present MARLUT, a new generalized and optimized LUT construction supporting multi-input tables over both rings $\mathbb{Z}_{2^k}$ and fields $\mathbb{F}_{2^k}$ with malicious security. We achieve this by (1) extending the semi-honest LUT protocol from MAESTRO, utilizing high-dimensional tensors to reduce its communication cost to $O(N^{1/3})$, and (2) designing a new distributed zero-knowledge proof for inner-product relations over $\mathbb{Z}_{2^k}$. Our distributed zero-knowledge proof is more efficient than the state-of-the-art work (Li et al., CCS 2024) and may be of independent interest. Experiments show that on a table of size $2^{16}$, our semi-honest LUT protocol reduces the offline computational and communication cost by a factor of $5.95$ and $3.23$, respectively. Our distributed zero-knowledge proofs show up to $7.07\times$ and $4.97\times$ speedups over the state-of-the-art protocol on ring $\mathbb{Z}_{2^8}$ and $\mathbb{Z}_{2^{16}}$, respectively.

@misc{cryptoeprint:2025/2109,
      author = {Chongrong Li and Pengfei Zhu and Yun Li and Zhanpeng Guo and Jingyu Li and Yuncong Hu and Zhicong Huang and Cheng Hong},
      title = {Secure Lookup Tables: Faster, Leaner, and More General},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/2109},
      year = {2025},
      url = {https://eprint.iacr.org/2025/2109}
}