Fully Homomorphic Encryption for Cyclotomic Prime Moduli

. This paper presents a Generalized BFV (GBFV) fully homomorphic encryption scheme that encrypts plaintext spaces of the form Z [ x ] / ( Φ m ( x ) , t ( x )) with Φ 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 Φ 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 plain-text spaces defined by a large cyclotomic prime, such as the Fermat prime Φ 2 (2 16 ) = 2 16 +1 and the Goldilocks prime Φ 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.