Welcome to the resource topic for 2024/1587
Title:
Fully Homomorphic Encryption for Cyclotomic Prime Moduli
Authors: Robin Geelen, Frederik Vercauteren
Abstract:This paper presents a Generalized BFV (GBFV) fully homomorphic encryption scheme that encrypts plaintext spaces of the form \mathbb{Z}[x]/(\Phi_m(x), t(x)) with \Phi_m(x) the m-th cyclotomic polynomial and t(x) an arbitrary polynomial. GBFV encompasses both BFV where t(x) = p is a constant, and the CLPX scheme (CT-RSA 2018) where m = 2^k and t(x) = x-b is a linear polynomial. The latter can encrypt a single huge integer modulo \Phi_m(b), has much lower noise growth than BFV (linear in m instead of exponential), but cannot be bootstrapped.
We show that by a clever choice of m and higher degree polynomial t(x), our scheme combines the SIMD capabilities of BFV with the low noise growth of CLPX, whilst still being efficiently bootstrappable. Moreover, we present parameter families that natively accommodate packed plaintext spaces defined by a large cyclotomic prime, such as the Fermat prime \Phi_2(2^{16}) = 2^{16} + 1 and the Goldilocks prime \Phi_6(2^{32}) = 2^{64} - 2^{32} + 1. These primes are often used in homomorphic encryption applications and zero-knowledge proof systems.
Due to the lower noise growth, e.g. for the Goldilocks prime, GBFV can evaluate circuits whose multiplicative depth is more than 5 times larger than native BFV. As a result, we can evaluate either larger circuits or work with much smaller ring dimensions. In particular, we can natively bootstrap GBFV at 128-bit security for a large prime, already at ring dimension 2^{14}, which was impossible before. We implemented the GBFV scheme on top of the SEAL library and achieve a latency of only 5 seconds to bootstrap a ciphertext encrypting 4096 elements modulo 2^{16}+1.
ePrint: https://eprint.iacr.org/2024/1587
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 .