Welcome to the resource topic for 2025/2109
Title:
Secure Lookup Tables: Faster, Leaner, and More General
Authors: Chongrong Li, Pengfei Zhu, Yun Li, Zhanpeng Guo, Jingyu Li, Yuncong Hu, Zhicong Huang, Cheng Hong
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.
ePrint: https://eprint.iacr.org/2025/2109
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .