Welcome to the resource topic for 2024/087
Title:
Tree-based Lookup Table on Batched Encrypted Queries using Homomorphic Encryption
Authors: Jung Hee Cheon, Hyeongmin Choe, Jai Hyun Park
Abstract:Homomorphic encryption (HE) is in the spotlight as a solution for privacy-related issues in various real-world scenarios. However, the limited types of operations supported by each HE scheme have been a major drawback in applications. While HE schemes based on learning-with-error (LWE) problem provide efficient lookup table (LUT) evaluation in terms of latency, they have downsides in arithmetic operations and low throughput compared to HE schemes based on ring LWE (RLWE) problem. The use of HE on circuits containing LUT has been partly limited if they contain arithmetic operations or their computational width is large.
In this paper, we propose homomorphic algorithms for batched queries on LUTs by using RLWE-based HE schemes. To look up encrypted LUTs of size n on encrypted queries, our algorithms use O(\log{n}) homomorphic comparisons and O(n) multiplications. For unencrypted LUTs, our algorithms use O(\log{n}) comparisons, O(\sqrt{n}) ciphertext multiplications, and O(n) scalar multiplications.
We provide a proof-of-concept implementation based on CKKS scheme (Asiacrypt 2017). The amortized running time for an encrypted (Resp. unencrypted) LUT of size 512 is 0.041 (Resp. 0.025) seconds. Our implementation reported roughly 2.4-$6.0$x higher throughput than the current implementation of LWE-based schemes, with more flexibility on the structure of the LUTs.
ePrint: https://eprint.iacr.org/2024/087
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 .