.png)
Digital privacy seems like an oxymoron these days. Whether through email, social media, or just by browsing the web, we share our private data so often that it is frequently at risk of exposure, misuse, and theft. This means that privacy is imperative if we want these tools to be both functional and confidential. While that may sound like a pipedream, we can already see advances in cryptography that help make this vision a reality.
Fully Homomorphic Encryption (FHE) allows for complete data privacy by allowing you to compute on encrypted data. In FHE, data inputs are encrypted and remain encrypted end-to-end, even through processing. When unvetted and untrusted parties are responsible for manipulating your data, the data is never revealed. FHE allows for the development of endless applications as a result. Private smart contracts with homomorphic encryption, facial recognition technology, voice assistants, and preventive medicine are just a few of the use cases, and the increasing user-friendliness of FHE means many more use cases will be presented in the near future.
Since FHE was first posed as a problem in the 1970s, many different schemes—and five main flavors—have helped to advance the technology. Let’s look at the history of FHE, including the genesis and evolution of modern schemes.
.png)
In 1978, a paper was published by Rivest, Adleman, and Dertouzos entitled “On Data Banks and Privacy Homomorphisms”1. Here, the idea of operating on encrypted data without decrypting it was first proposed, and it was pure fantasy at the time: “It remains to be seen whether it is possible to have a privacy homomorphism with a large set of operations which is highly secure.” Over 20 years later, that fantasy became a distinct possibility.
At Eurocrypt ‘99, cryptographer and current Zama CTO Pascal Paillier presented an additive homomorphic cryptosystem in his paper “Public-Key Cryptosystems Based on Composite Degree Residuosity Classes2", which sought to investigate the Composite Residuosity Class Problem. Furthering the idea of privacy homomorphisms, the Paillier system created a trapdoor in the discrete log, providing “a new cryptographic building-block for conceiving public-key cryptosystems.” Though still partially homomorphic, the scheme had clear applications related to electronic voting, cryptocurrencies, and threshold cryptography.
Another decade would pass before the advent of the first plausible fully homomorphic encryption scheme3.Craig Gentry (2009) outlined a bootstrapping technique which allowed for noise reduction, making advanced computation possible. Bootstrapping applies the decryption function homomorphically; during this process the data remains encrypted, but the level of noise is reduced. Bootstrapping was a breakthrough that finally made FHE achievable, even if slow processing speeds were a concern.
What stemmed from Gentry’s work on FHE was the BGV scheme4 (2011). Brakerski and Vaikuntanathan used Learning With Errors (LWE) as their foundation while shortening ciphertexts and reducing decryption complexity. The BGV scheme relied on the conversion of a somewhat homomorphic scheme into a fully homomorphic one, utilizing bootstrapping for improved efficiency.
The Brakerski/Fan-Vercauteren scheme, BFV5(2012), came next. Published just nine months after BGV, it focused on a “down to earth approach” that attempted to do away with “excess mathematical machinery.” BFV utilized Ring Learning With Errors (RLWE) setting and relied upon scale-invariance and relinearization to create more flexibility. Offering clear parameters for BFV further increased efficiency and computation speed while simplifying the bootstrapping process. This scheme is considered one of the first truly practical FHE schemes.
An advanced approach to leveled schemes, Cheon, Kim, Kim and Song proposed the CKKS7method in 2016. Using block floating point arithmetic drastically reduced latency, but errors generated due to the approximate nature of the scheme sometimes cause critical security concerns. Error reduction has therefore been a main focus of further development.
While purely leveled schemes have their place in FHE development, what truly limits them is their versatility. As processing improves, the issue that leveled schemes face is their need to provide fixed, pre-programmed parameters for computation. What caused a definitive divide in the FHE landscape was the need for computation to be both accurate and scalable, preferably without any limitations.
Recognizing these limitations, an alternate branch of FHE formed, which does away with relinearization and makes continued progress with noise reduction. Bootstrapping became more efficient with the Gentry-Sahai-Waters cryptosystem, with two main schemes developing from GSW: FHEW and TFHE.
FHEW6, introduced in 2014, offered the ability to homomorphically compute simple bit operations while bootstrapping the outputs, therefore reducing processing speed from roughly 6 minutes per batch to around 0.69 seconds. FHEW focused on improving bootstrapping, referring to it as the “main bottleneck in any practical implementation” of FHE. Ducas and Micciancio effectively demonstrated that “macroscopic delays are not a necessary requirement of bootstrapped FHE computations, and bootstrapping itself can be achieved at much higher speeds than previously thought possible.” Adding the homomorphic NAND operation during bootstrapping and utilizing RLWE helped to reduce latency and further highlight the practicality of FHE.
Released in 2016, TFHE8 initially improved upon FHEW, adding more functionality and dramatically upgrading processing speed. Chillotti, Gama, Georgieva, and Izabachène improved latency to less than 0.1 seconds per gate bootstrapping operation. The scheme has since developed programmable bootstrapping into its process, speeding up FHE to make it practical for most use cases, both for web2 and web3 applications. Programmable bootstrapping enables the homomorphic evaluation of any function represented as a table lookup over a ciphertext with a controlled level of noise. For problems involving circuits of considerable depth and complexity, only this bootstrapped mode is applicable. Deep neural networks and other machine learning techniques are prime use cases for libraries built on the TFHE scheme using programmable bootstrapping. The first implementation of a TFHE library was only for boolean circuits, but today’s state-of-the-art implementations, such as Zama’s TFHE-rs, extend the original capabilities of TFHE to support programmable bootstrapping over integers.
The history of FHE is substantial, and work is still being done to improve processes and processing. Latency issues often take center stage when discussing FHE, though time and focused development will see continued improvement to the speed of programmable bootstrapping operations. Future development will focus on functionality and security, which will help make FHE one of the fundamental methods of digital privacy protection.
—
Resources (in order of appearance):
1. Rivest, R., Adleman, L., and Dertouzos, M. (1978). On Data Banks and Privacy Homomorphisms. Massachusetts Institute of Technology. Cambridge, Massachusetts.
Paper link, Penn State University: https://citeseerx.ist.psu.edu
2.Paillier, P. (1999). Public-Key Cryptosystems Based on Composite Degree Residuosity Classes. In: Stern, J. (eds) Advances in Cryptology — EUROCRYPT ’99. EUROCRYPT 1999. Lecture Notes in Computer Science, vol 1592. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-48910-X_16
Paper link, Springer: https://rdcu.be/c9UGr
3. Gentry, C. (2009). A Fully Homomorphic Encryption Scheme. Stanford University. Stanford, California. Paper Link, Stanford University: https://crypto.stanford.edu/craig/craig-thesis.pdf
Paper Link, Evervault: https://evervault.com/papers/gentry.pdf
4. Brakerski, Zvika, and Vinod Vaikuntanathan. (2011). Efficient Fully Homomorphic Encryption from (Standard) LWE. In: SIAM Journal on Computing, vol. 43, no. 2, Jan. 2014, pp. 831–71. © The Authors. http://dx.doi.org/10.1137/120868669
Paper Link, Massachusetts Institute of Technology: https://dspace.mit.edu/
5. Fan, J. and Vercauteren, F. (2012).Somewhat Practical Fully Homomorphic Encryption.
Paper Link, ePrint: https://eprint.iacr.org/2012/144
6. Ducas, L. and Micciancio, D. (2014). FHEW: Bootstrapping Homomorphic Encryption in less than a second.
Paper Link, Springer: https://link.springer.com/chapter/10.1007/978-3-662-46800-5_24Paper Link, ePrint: https://eprint.iacr.org/2014/816
7. Cheon, J.H., Kim, A., Kim, M., Song, Y. (2016). Homomorphic Encryption for Arithmetic of Approximate Numbers
Paper Link, ePrint: https://eprint.iacr.org/2016/421
8. Chillotti, I., Gama, N., Georgieva, M., Izabachène, M. (2016). Faster Fully Homomorphic Encryption: Bootstrapping in Less Than 0.1 Seconds. In: Cheon, J., Takagi, T. (eds) Advances in Cryptology – ASIACRYPT 2016. ASIACRYPT 2016. Lecture Notes in Computer Science(), vol 10031. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-53887-6_1
Paper link, Springer: https://rdcu.be/c9QTW