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 , 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)  scheme. The Brakerski/Fan-Vercauteren (BFV) [2, 3] and the Cheon-Kim-Kim-Song (CKKS)  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:
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 . Information about noise growth in BFV is scattered throughout . 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 . 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 .
While additions of ciphertexts can be performed almost indiscriminately (within reason), multiplying two ciphertexts together increases noise the most. For ’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 .
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: