Paper 2024/1587

Fully Homomorphic Encryption for Cyclotomic Prime Moduli

Abstract

This paper presents a Generalized BFV (GBFV) fully homomorphic encryption scheme that encrypts plaintext spaces of the form $\mathbb{Z}[x]/({\mathrm{\Phi }}_m(x),t(x))$ with ${\mathrm{\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 ${\mathrm{\Phi }}_m(b)$, has much lower noise growth than BFV, but it is not known to be efficiently bootstrappable. We show that by a clever choice of $$ and higher degree polynomial $$, 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 $$ and the Goldilocks prime $$. These primes are often used in homomorphic encryption applications and zero-knowledge proof systems. Due to the lower noise growth, GBFV can evaluate much deeper circuits compared to native BFV in the same ring dimension. As a result, we can evaluate either larger circuits or work with smaller ring dimensions. In particular, we can natively bootstrap GBFV at 128-bit security already at ring dimension $$, which was impossible before. We implemented the GBFV scheme on top of the SEAL library and achieve a latency of only 2 seconds to bootstrap a ciphertext encrypting up to 8192 elements modulo $$.