Tree-based lookup table on batched encrypted queries using homomorphic encryption
This paper addresses the problem of evaluating lookup tables (LUTs) on encrypted queries within the framework of homomorphic encryption (HE), specifically investigating how ring learning-with-errors (RLWE)-based schemes can be leveraged for operations traditionally considered more suitable for LWE-based schemes.\N\NThe principal contribution of this work consists in the design of three tree-based algorithms for batched LUT evaluation under RLWE-based HE, achieving \(O(\log n)\) homomorphic comparisons and \(O(n)\) multiplications for encrypted LUTs, and \(O(\log n)\) comparisons with \(O(\sqrt{n})\) ciphertext multiplications and \(O(n)\) scalar multiplications for unencrypted LUTs, accompanied by a proof-of-concept implementation on the CKKS scheme that reports amortized running times of \(0.041\)~seconds and \(0.025\)~seconds per query for encrypted and unencrypted LUTs of size~\(512\), respectively.\N\NThe research situates itself within a broader line of investigation on efficient homomorphic computation for non-arithmetic functions. The authors position their algorithms against LWE-based programmable bootstrapping approaches such as TFHE and FHEW, which are inherently limited by small plaintext spaces (at most \(8\) bits) and thus cannot directly handle larger or real-valued lookup tables. The paper explicitly engages with the CKKS-based method introduced in Bleach [\textit{N. Drucker} et al., J. Cryptology 37, No. 1, Paper No. 3, 35 p. (2024; Zbl 1527.94032)], which requires \(O(n \log n)\) homomorphic multiplications for one-hot vector generation, and reduces this to \(O(n)\). The connection to the one-hot map generation technique of \textit{E. Aharoni} et al. [``Generating one-hot maps under encryption, Lect. Notes Comput. Sci. 13914, 96--116 (2023; \url{doi.org/10.1007/978-3-031-34671-2_8})]. is also acknowledged, as is the tree-based range search approach of \textit{E. Kushnir} et al. [``Secure range-searching using copy-and-recurse, Cryptology ePrint Archive, Paper 2023/983 (2023), \url{https://ia.cr/2023/983}], whose copy-and-recurse technique bears structural similarity to the folding algorithm proposed here. The hybrid baby-step/giant-step strategy introduced as Algorithm~3 combines the complementary cost profiles of the one-hot indicator and table folding approaches, achieving a reduction in ciphertext multiplications from \(O(n)\) to \(O(\sqrt{n})\) for unencrypted tables while maintaining the same \(O(\log n)\) comparison complexity. Additionally, the adaptation to approximate arithmetic in Section~4, including the error propagation analysis through \(\log n\) iterations of approximate comparison (Theorem~4.1), and the heuristic randomization of table keys via Chebyshev polynomials (Algorithm~4) to mitigate pathological \(\Delta\) values, provide practical considerations for deployment on the CKKS scheme.\N\NThe results find direct applicability in privacy-preserving machine learning inference scenarios, particularly in the machine-learning-as-a-service (MLaaS) paradigm described in Section~1, where clients delegate computation on encrypted data to untrusted servers. The authors note that discrete non-arithmetic functions, including activation and loss functions commonly encountered in neural network evaluation, can be represented as lookup tables and thus evaluated using the proposed algorithms. The non-interactive nature of the protocol and the compatibility of the output format with subsequent RLWE-based arithmetic operations make the algorithms suitable as building blocks within larger homomorphic circuits. The throughput improvement of \(2.4\)--\(6.0\times\) over current LWE-based implementations, as reported in Section~5, is relevant for applications requiring batch processing of multiple queries on the same table structure.\N\NSeveral aspects remain unaddressed and constitute directions for future investigation. The experimental evaluation is limited to uniformly distributed table keys, and the paper explicitly states that the Chebyshev-based key randomization (Algorithm~4) was not included in the implementation. The practical behavior of the algorithms on non-uniform or adversarially distributed key sets, where \(\Delta\) may be extremely small, thus remains empirically uncharacterized. The algorithms assume sorted lookup tables for the encrypted case and defer to existing homomorphic sorting methods, yet the combined cost of sorting and lookup is not analyzed. The security model considered is restricted to IND-CPA, and no discussion of stronger notions such as circuit privacy or protection against side-channel leakage through access patterns is provided. Furthermore, the multi-threaded performance and scalability behavior are not explored, as all experiments are conducted on a single thread. The generalization mentioned in Remark~3.5, concerning \(c\)-way table splitting with SIMD-parallel comparisons, is stated without experimental validation. Finally, the paper does not address the interplay between the proposed LUT evaluation and bootstrapping costs that would arise in deeper circuits requiring ciphertext refreshing between successive LUT evaluations.
- (Leveled) fully homomorphic encryption without bootstrapping
- BLEACH: cleaning errors in discrete computations over CKKS
- Bootstrapping for approximate homomorphic encryption
- CHIMERA: combining ring-LWE-based fully homomorphic encryption schemes
- Efficient homomorphic comparison methods with optimal complexity
- FHEW: bootstrapping homomorphic encryption in less than a second
- HERMES: efficient ring packing using MLWE ciphertexts and application to transciphering
- Homomorphic encryption for arithmetic of approximate numbers
- Numerical method for comparison on homomorphically encrypted numbers
- On the Number of Nonscalar Multiplications Necessary to Evaluate Polynomials
- Parameter optimization and larger precision for (T)FHE
- TFHE: fast fully homomorphic encryption over the torus
This page was built for publication: Tree-based lookup table on batched encrypted queries using homomorphic encryption
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6880357)
