Homomorphic Encryption for Beginners: A Practical Guide (Part 1)
I will first go over the basics of homomorphic encryption, followed by a brief overview of the open source homomorphic encryption libraries that are currently available, then will finish with a tutorial on how to use one of those libraries (namely, PALISADE). For this guide, I am assuming a background in basic cryptography, abstract algebra, and C++.
A Brief Introduction to Homomorphic Encryption
The concept of homomorphic encryption was introduced in [1], of which two of the authors are Ronald L. Rivest and Len Alderman. The R and the A in RSA encryption.
The most popular example for the use of homomorphic encryption is where a data owner wants to send data up to the cloud for processing, but does not trust a service provider with their data. Using a homomorphic encryption scheme, the data owner encrypts their data and sends it to the server. The server performs the relevant computations on the data without ever decrypting it and sends the encrypted results to the data owner. The data owner is the only one able to decrypt the results, since they alone have the secret key.
So far, the most efficient homomorphic encryption scheme when performing the same operations on multiple ciphertexts at once is the Brakerski-Gentry-Vaikuntanathan (BGV) [11] scheme. The Brakerski/Fan-Vercauteren (BFV) [2, 3] and the Cheon-Kim-Kim-Song (CKKS) [4] schemes share second place for efficiency. BGV is, however, more difficult to use. These are all lattice-based cryptographic schemes dependent on the hardness of the Ring Learning With Errors (RLWE) problem, which (at least for now) means that they are quantum-safe. For an excellent introduction of lattices and the hard problem that RLWE is based on (namely, the Shortest Vector Problem) see these two lectures by MIT Professor Vinod Vaikuntanathan:
https://www.youtube.com/watch?v=LlPXfy6bKIY
https://www.youtube.com/watch?v=SZkTJMorxnM
BGV, BFV, and CKKS are additively and multiplicatively homomorphic (i.e., you can perform both addition and multiplication within the encrypted domain). No division. No exponentiating a number by an encrypted one. No non-polynomial operations. In BGV and BFV, computations can only be performed on integers. In CKKS, computations can be performed on complex numbers with limited precision.
A catch is that you cannot perform unlimited computations within the encrypted domain without running into two issues:
Issue 1: In BGV and BFV, you have to keep track of what is called the plaintext modulus p. Simply, imagine you have p=9 and that you do enc(4) + enc(8) = enc(3) (mod 9). When you decrypt enc(3), if you weren’t careful, you would have no way of knowing whether the actual result was really meant to be 3, 12, 21, …
Issue 2: In both schemes, you have to make sure you don’t go over the noise threshold, above which your values will no longer make any sense. The hardness of RLWE is based on adding a small amount of error to a point in a lattice, such that it is difficult to determine which point that error was originally added to. For more on noise growth in CKKS, see pages 12 and 22 of [4]. Information about noise growth in BFV is scattered throughout [3]. The reason BGV is more difficult to use than BFV and CKKS is that the noise levels need to be kept track of at every single step of the algorithm.
Noise can be dealt with by using bootstrapping, famously introduced by Craig Gentry as the very first method enabling unlimited computations to be made in the encrypted domain [5]. Homomorphic encryption without an upper bound on the number of computations that can be performed is called fully homomorphic encryption (FHE), as opposed to somewhat homomorphic encryption (SHE). If anyone requests it, I can explain bootstrapping in another post.
Since bootstrapping is an expensive operation, it is best to avoid using it unless you really need to. What BFV and CKKS use to allow for multiple ciphertext multiplications to be performed is the scale-invariant error-reduction technique explained in [2].
While additions of ciphertexts can be performed almost indiscriminately (within reason), multiplying two ciphertexts together increases noise the most. For [2]’s scale-invariant method to work, you need to already know how many multiplications you will perform when you are generating the cryptographic parameters. Whenever possible, you should choose to multiply ciphertexts with plaintexts or add ciphertexts with plaintexts, as operations with plaintexts hardly affects the noise growth.
If you are planning on performing the same operations on multiple ciphertexts, you should consider using the Single-Instruction-Multiple-Data (SIMD) method, based on the Chinese Remainder Theorem, described in [9,10]. This optimization should be implemented in any homomorphic encryption library worth its salt.
Phew… those are most of the constraints within which you will have to work in order to write code using HE. For more really clear information on the BFV scheme, please see [8].
Homomorphic Encryption Libraries
There are five open source homomorphic encryption libraries that I’ve heard good things about:
Of these five, I’ve personally used PALISADE, SEAL, and HElib. All three implement the BFV scheme. SEAL and HElib both implement CKKS as well.
PALISADE is a DARPA and IARPA-funded project (previously NSA-funded too). It was developed and is supported by a superbly talented team at the New Jersey Institute of Technology (Gerard Ryan, Professor Yuriy Polyakov, and Professor Kurt Rohloff).
SEAL was developed by the Microsoft Research Cryptography Research Group.
HElib was developed by Shai Halevi and Victor Shoup, both esteemed figures in the cryptographic community. The library does, however, have less support than PALISADE and SEAL do.
TFHE implements a scheme that is faster than BGV for individual operations, but which cannot make use of the SIMD method mentioned above.
PALISADE, HElib, and SEAL can be freely used within commercial applications, with each using an NJIT license, Apache v2.0 license, and MIT license respectively.
A Tutorial on PALISADE
First,clone the repo, and then set up the environment in Linux (Windows is no longer supported). The best way to learn how to use any of the homomorphic encryption libraries is to look at the examples (PALISADE\src\pke\demo). For PALISADE, the scheme you want to use is called BFVrns. BFV and BVG are not as efficient and the LTV scheme is not secure.
We will be generating a public key cryptosystem that allows for addition and multiplication within the encrypted domain.
To generate the encryption parameters and save them, you can use the following code, which you can essentially find within the PALISADE demos:
Note that the larger the plaintext modulus, the longer the calculations will take within the encrypted domain.
You can print out the parameters that were generated:
You can determine how secure your parameters are by comparing them to the ones suggested in the Homomorphic Encryption Standard [8]. The parameters generated by the code above give us 128-bit security, meaning that it would take roughly 2¹²⁸ computations in order to crack the secret key.
Next, you will need to generate keys for evaluating addition and multiplication operations:
Whenever possible, you will want to use the SIMD method mentioned earlier. In PALISADE, you can do so by creating a vector with the numbers you want to operate on, packing those numbers into a Plaintext, and encrypting that Plaintext:
Recall that we are working with a polynomial ring. CT1 should be interpreted as the encrypted coefficients of the polynomial 0x⁴ + 4x³ + 6x² + 2x + 5 and CT2 as the encrypted coefficients of 1x⁴ + 6x³ + 3x² + 5x + 2. The sum of these two ciphertexts can be seen as the sum of two polynomials within the encrypted domain, resulting in 1x⁴ + 10x³ + 9x² +7x + 7. Whereas, their component-wise multiplication results in 0x⁴ + 24x³ + 18x² +10x + 10. Had we used MakeCoeffPackedPlaintext(v1) and MakeCoeffPackedPlaintext(v2) instead instead of MakePackedPlaintext(v1) and MakePackedPlaintext(v2), multiplying CT1 by CT2 would have resulted in a ciphertext representing the coefficients of 4x⁷+30x⁶+50x⁵+55x⁴+74x³+37x²+29x+10.
To decrypt and see the result of the inner product:
If anyone has a special request for what I should include in part 2 of this tutorial (be it theoretical or practical), do feel free to message me at pthaine AT cs DOT toronto DOT edu.
Acknowledgements
I am tremendously grateful to the PALISADE team for their attentiveness to questions about their library and to Dr. Shai Halevi for his suggestions on how to improve the original version of this post.
References
[1] Rivest, R. L., Adleman, L., & Dertouzos, M. L. (1978). On data banks and privacy homomorphisms. Foundations of secure computation, 4(11), 169–180.
[2] Brakerski, Z. (2012). Fully homomorphic encryption without modulus switching from classical GapSVP. In Advances in cryptology–crypto 2012 (pp. 868–886). Springer, Berlin, Heidelberg.
[3] Fan, J., & Vercauteren, F. (2012). Somewhat Practical Fully Homomorphic Encryption. IACR Cryptology ePrint Archive, 2012, 144.
[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] Gentry, C., & Boneh, D. (2009). A fully homomorphic encryption scheme (Vol. 20, №09). Stanford: Stanford University.
[6] Brakerski, Z., Gentry, C., & Vaikuntanathan, V. (2014). (Leveled) fully homomorphic encryption without bootstrapping. ACM Transactions on Computation Theory (TOCT), 6(3), 13.
[7] Smart, N. P., & Vercauteren, F. (2014). Fully homomorphic SIMD operations. Designs, codes and cryptography, 71(1), 57–81.
[8] Albrecht, M.; Chase, M.; Chen, H.; Ding, J.; Goldwasser, S.; Gorbunov, S.; Hoffstein, J.; Lauter, K.; Lokam, S.; Micciancio, D.; Moody, D.; Morrison, T.; Sahai, A.; and Vaikuntanathan, V. 2018. Homomorphic encryption security standard. Technical report, HomomorphicEncryption.org, Cambridge MA.
[9] Gentry, Craig, Shai Halevi, and Nigel P. Smart. “Fully homomorphic encryption with polylog overhead.” Annual International Conference on the Theory and Applications of Cryptographic Techniques. Springer,
Berlin, Heidelberg, 2012.
[10] Smart, Nigel P., and Frederik Vercauteren. “Fully homomorphic SIMD operations.” Designs, codes and cryptography 71.1 (2014): 57–81.
[11] Brakerski, Zvika, Craig Gentry, and Vinod Vaikuntanathan. “(Leveled) fully homomorphic encryption without bootstrapping.” ACM Transactions on Computation Theory (TOCT) 6.3.
Appendix
If you plan on reusing your keys, you can serialize them and store them in text files:
You can retrieve all of your keys, parameters, and cryptocontext as follows:
