Amortized Large Look-up Table Evaluation with Multivariate Polynomials for Homomorphic Encryption

ePrint Report: Amortized Large Look-up Table Evaluation with Multivariate Polynomials for Homomorphic Encryption

Heewon Chung, Hyojun Kim, Young-Sik Kim, Yongwoo Lee

We present a new method for efficient look-up table (LUT) evaluation in homomorphic encryption (HE), based on Ring-LWE-based HE schemes, including both integer-message schemes such as Brakerski-Gentry-Vaikuntanathan (BGV) and Brakerski/Fan-Vercauteren (BFV), and complex-number-message schemes like the Cheon-Kim-Kim-Song (CKKS) scheme. Our approach encodes bit streams into codewords and translates LUTs into low-degree multivariate polynomials, allowing for the simultaneous evaluation of …

encryption eprint report evaluation homomorphic encryption integer kim large lee message report ring young