The Rise and Rise of Homomorphic Encryption

There are three main places where data can exist: at-rest, over-air, and in-memory. While we have good levels of encryption for at-rest and…
Photo by Towfiqu barbhuiya on Unsplash

The Rise and Rise of Homomorphic Encryption

There are three main places where data can exist: at-rest, over-air, and in-memory. While we have good levels of encryption for at-rest and over-air, it is in-memory that leaves data unprotected. And, it doesn’t have to be this way — it is just the way we have designed our processors. A future system architecture might see the processing of encrypted values and thus the rise of what is called homomorphic encryption. And, so, researchers have been busily working on open source code, and which could scale to virtually any programming language that we want. One great advancement is this new paper and its associated GitHub code [here]:

Figure 1

With this, there have basically been four main generations of homomorphic encryption (Figure 2):

  • 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]. Here.
Figure 2

The current version of the code implements [here][5]:

  • Brakerski/Fan-Vercauteren (BFV) scheme for integer arithmetic
  • Brakerski-Gentry-Vaikuntanathan (BGV) scheme for integer arithmetic
  • Cheon-Kim-Kim-Song (CKKS) scheme for real-number arithmetic (includes approximate bootstrapping)
  • Ducas-Micciancio (DM) and Chillotti-Gama-Georgieva-Izabachene (CGGI) schemes for Boolean circuit evaluation.

The 1st Generation

Craig Gentry was the first to show an implementation of fully homomorphic encryption (FHE), and received the 2009 ACM Doctoral Dissertation Award for this breakthrough work. The concept of homomorphic encryption, though, had been around since public key encryption itself, and partial homomorphic methods included Paillier [here] and RSA [here]:

Figure 3 [6]

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:

Figure 4

The 2nd generation: Dijk, Gentry, Halevi and Vaikuntanathan

The work of Gentry was then advanced, and, in 2010, DGHV (Dijk, Gentry, Halevi and Vaikuntanathan) defined an expansion into the usage of integers:

Figure 5

With these methods, we encrypt our data, and then input these cipher bits into a 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.

The 4th Generation: CKKS

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:

Figure 6: Ref

Applying homomorphic encryption

In a recent presentation, Craig also outlined that three important application areas were within privacy-preserving genome association, neural networks, and private information retrieval:

Figure 6: Ref

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

And, so, now, we have a foundation to build on, and there are no excuses for system architecture to avoid the usage of homomorphic encryption. Here’s to the future of a more secret “in process” world. You can learn more here:

https://asecuritysite.com/homomorphic/

But, the performance hit can be a limiting factor, so don’t dismiss the usage of partial homomorphic methods, such as ElGamal:

  • ElGamal Homomorphic Cipher (Go). ElGamal. This outlines ElGamal Homomorphic cipher with Go.
  • ElGamal Homomorphic Cipher (Go) — Divide. ElGamal. This outlines ElGamal Homomorphic cipher with Go with divide.
  • ElGamal Homomorphic Cipher (Go) — Additive. ElGamal. This outlines ElGamal Homomorphic cipher with Go with addition.
  • ElGamal Homomorphic Cipher for Multiplication (Python). ElGamal. This outlines ElGamal Homomorphic multiplication with Python.
  • ElGamal Homomorphic Cipher for Division (Python). ElGamal. This outlines ElGamal Homomorphic division with Python.
  • ElGamal Homomorphic Cipher for Addition (Python). ElGamal. This outlines ElGamal Homomorphic addition with Python.
  • ElGamal Homomorphic Cipher for Subtraction (Python). ElGamal. This outlines ElGamal Homomorphic subtraction with Python.

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.

[5] https://github.com/openfheorg/openfhe-development

[6] Paillier, P. (1999, May). Public-key cryptosystems based on composite degree residuosity classes. In International conference on the theory and applications of cryptographic techniques (pp. 223–238). Springer, Berlin, Heidelberg.