Four Generations of Homomorphic Encryption And An Eigth-fold Improvement Each Year … As Defined By…
Four Generations of Homomorphic Encryption And An Eight-fold Improvement Each Year … As Defined By Craig Gentry
The dream for cybersecurity is that data is protected at rest, over-air and in-process. While we often use encryption to store data (“at rest), and use TLS and tunnels to protect over the network (“over air”), we still do not encrypt in-process. It is there that intruders can capture sensitive data, such as with the running memory or within the registers of the CPU. For this, we could look to use homomorphic encryption to protect data in every part of its journey, and still be able to process it.
At Eurocrypt 2021, the inventor of the first fully homomorphic encryption method — Craig Gentry — gave his thoughts on the past 10 years since he published his PhD thesis:
Craig received the 2009 ACM Doctoral Dissertation Award for this breakthrough work on homomorphic encryption. The concept of homomorphic encryption, though, had been around since public key encryption itself, and partial homomorphic methods included Paillier [here] and RSA [here]:
Overall, homomorphic encryption can either be partially homomorphic (PHE), somewhat homomorphic, levelled fully homomorphic, or fully homomorphic encryption (FHE). For security, the best case is fully homomorphic encryption. Craig’s published work on homomorphic encryption started in 2019 with the first useable fully homomorphic encryption (FHE) method:
Followed in 2010 by DGHV (Dijk, Gentry, Halevi and Vaikuntanathan) method:
With these methods, we encrypt our data, and then input these cipher bits into an cipher circuit. A basic adding function is here:
https://asecuritysite.com/homomorphic/hom_adder
Overall it was not possible to examine any of the bits in the circuit to discover the original state of the plaintext. On the output of the circuit, we could then decrypt the cipher bits back into the cipher text. For this we could create and function or arithmetic operation that we wanted … it basically all comes down to EX-OR (adding) and AND (multiplication) operations.
Within Craig’s talk, he outlined that there had been four generations of homomorphic encryption:
- 1st generation: Gentry’s method uses integers and lattices [1] including the DGHV method. A demo is here.
- 2nd generation. Brakerski, Gentry and Vaikuntanathan’s (BGV) work in 2014 for FHE using Learning With Errors [2]. A demo is here.
- 3rd generation: Lattice-based methods as defined by Brakerski and Vaikuntanathan [3].
- 4th generation: CKKS (Cheon, Kim, Kim, Song) and which uses floating-point numbers [4].
HEAAN (Homomorphic Encryption for Arithmetic of Approximate Numbers) defines a homomorphic encryption (HE) library proposed by Cheon, Kim, Kim and Song (CKKS). The CKKS method uses approximate arithmetics over complex numbers [paper]. Overall it is a levelled approach, and which involves the evaluation of arbitrary circuits of bounded (pre-determined) depth. These circuits can include ADD (X-OR) and Multiply (AND).
HEAAN uses a rescaling procedure for the size of the plaintext. It then produces an approximate rounding due to the truncation of the ciphertext into a smaller modulus. The method is especially useful in that it can be applied to carry out encryption computations in parallel. Unfortunately, the ciphertext modulus can become too small, and where it is not possible to carry out any more operations.
The HEAAN (CKKS) method uses approximate arithmetic over complex numbers (ℂ), and is based on Ring Learning With Errors (RLWE). It focuses on defining an encryption error within the computational error that will happen within approximate computations. We initially take a message (M) and convert to a cipher message (ct) using a secret key sk. To decrypt ([⟨ct,sk⟩]q), we produce an approximate value along with a small error (e).
I have implemented an example of HEEAN here:
https://asecuritysite.com/homomorphic/go_lattice_cc
and an example of adding, subtracting and multiplying here:
https://asecuritysite.com/homomorphic/go_lattice_cc5
With CKKS and CKKS+, he observed the amazing improvements in performance, with HE getting eight times faster each year:
Craig also outlined that three important application areas were within privacy-preserving genome association, neural networks, and private information retrieval:
Along with this, he proposed that the research community should investigate new methods which did not involve the usage of lattices. One might worry that we could achieve the limits of advancement with lattices, and that (perhaps) a weakness could be discovered in their approach, and bring down the whole area.
Conclusions
It was a great talk and a great recap of a decade of breathtaking work. Overall it has shown how the research community can discover new areas, and then for research teams to pick these up and drive them forward. There are not many areas of science that can point to an eight-fold improvement in each year, but the crypto community have managed this. If you are interested in homomorphic encryption, come and work with us in the Blockpass ID Lab, or have a look here:
https://asecuritysite.com/homomorphic/
References
[1] Van Dijk, M., Gentry, C., Halevi, S., & Vaikuntanathan, V. (2010, May). Fully homomorphic encryption over the integers. In Annual international conference on the theory and applications of cryptographic techniques (pp. 24–43). Springer, Berlin, Heidelberg.
[2] Brakerski, Zvika, and Vinod Vaikuntanathan. “Efficient fully homomorphic encryption from (standard) LWE.” SIAM Journal on Computing 43.2 (2014): 831–871.
[3] Brakerski, Z., & Vaikuntanathan, V. (2014, January). Lattice-based FHE as secure as PKE. In Proceedings of the 5th conference on Innovations in theoretical computer science (pp. 1–12).
[4] Cheon, J. H., Kim, A., Kim, M., & Song, Y. (2017, December). Homomorphic encryption for arithmetic of approximate numbers. In International Conference on the Theory and Application of Cryptology and Information Security (pp. 409–437). Springer, Cham.