November 2022 Summaries

Since the introduction of the first fully homomorphic encryption (FHE) scheme by Gentry in 2009, various constructions have been proposed, primarily based on hard lattice problems, but many faced security challenges. Notably, schemes based on ideal lattices and NTRU assumptions were deemed insecure due to over-stretched parameters, while Learning-with-Errors (LWE) and its ring counterpart (Ring-LWE) form the basis of more secure schemes like BGV, BFV, CKKS, and GSW. Recent research by KU Leuven and Zama, presented at AsiaCrypt 2022, revisits NTRU-based constructions with a novel approach that avoids the parameter overstretching issue by integrating methods from GSW, FHEW, and TFHE systems. This new NTRU-based FHE scheme potentially restores the efficiency advantage of using a single ring element per ciphertext, although further optimization and research are required to determine if it can rival existing TFHE implementations.

Zama has launched the Zama Bounty Program to advance the field of Fully Homomorphic Encryption (FHE) by engaging the community through a system of rewards for contributions rather than just bug detection. This initiative is structured into quarterly bounties categorized as Easy, Expert, Moonshot, and Open Bounties, with prizes ranging from €500 to an unlimited amount. The Easy Bounties are designed for beginners, while Expert and Moonshot Bounties require significant expertise and could potentially revolutionize the FHE landscape. Participants can apply to tackle these challenges, and their work is reviewed by Zama and possibly external reviewers at the end of each quarter to decide on the distribution of rewards. This approach stems from Zama's belief that significant breakthroughs often originate from unexpected contributors, thus fostering innovation beyond the company's existing talent pool.

Bootstrapping in the context of Fully Homomorphic Encryption (FHE) is a method used to manage the noise and levels associated with encrypted ciphertexts, allowing for continuous computation without degrading data integrity. Different FHE schemes, such as BGV/BFV, CKKS, and TFHE, utilize bootstrapping in distinct ways, impacting the latency and throughput of operations. BGV/BFV schemes increase both the level and reduce noise, CKKS increases level but maintains noise, while TFHE significantly reduces latency and allows for programmable bootstrapping, providing a richer computational language. Despite its computational expense, bootstrapping is essential for performing deep circuit evaluations, and advancements in hardware acceleration have improved its efficiency across different schemes. Understanding the nuances of bootstrapping in each scheme is crucial for optimizing performance and effectively implementing FHE in practical applications.

Fully homomorphic encryption (FHE) allows operations to be performed directly on encrypted data, with bootstrapping serving as a crucial technique to manage the inherent noise in ciphertexts, which increases during operations but is essential for security. In TFHE, bootstrapping, and its programmable extension, is notably efficient, primarily through polynomial multiplications evaluated in the Fourier domain using either the fast Fourier transform (FFT) or its discrete counterpart, the number-theoretic variant (NTT). While NTT offers exact results, it restricts the choice of modulus, typically requiring NTT-friendly moduli. The work presented at WAHC 2022 proposes an alternative by altering the quotient polynomial, expanding the programmable bootstrapping framework to encompass a polynomial ring $(ℤ/qℤ)[X]/(Φ(X))$ with a cyclotomic polynomial $Φ(X)$, advantageous when modulus $q$ is a power of two. The paper includes example parameters to illustrate this approach.