Secure Lookup Tables: Faster, Leaner, and More General

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\left(N^{1 / 2}\right)$; 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\left(N^{1 / 2}\right)$ 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\left(N^{1 / 3}\right)$, 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 216, 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.