Homomorphic Encryption 101

Fully Homomorphic Encryption (FHE) has long been considered as the holy grail of cryptography. The concept was imagined in the late seventies, but the first realization only came three decades later. Today, both the public and private sectors are embracing this new security paradigm and are actively working at making FHE more practical and easier to use.

The journey started in 1978. Ron Rivest, Len Adleman (the “R” and “A” of the celebrated RSA cryptosystem), and Michael Dertouzos imagine resorting to “homomorphisms” for the user’s privacy and introduce what is known today as Fully Homomorphic Encryption or FHE.

What is FHE?

Encryption enables the protection of sensitive data while it is stored or when it needs to be transferred. However, standard encryption technologies require data to be decrypted to be processed. The idea behind homomorphic encryption is to never decrypt and to directly compute on encrypted data. It bears its name from the mathematical notion of homomorphism: elements of one set are transformed to elements of a second set while maintaining the relationships between the elements of the two sets.

Applied to encryption, this means that operating on plaintexts (i.e., unencrypted data) or on ciphertexts (i.e., encrypted data) will yield an equivalent result — in the clear when operating on plaintexts and under an encrypted form when operating on ciphertexts. For example, given any two ciphertexts c₁ and c₂ respectively encrypting plaintexts x₁ and x₂, there exists a public operation ⊕ such that c₃=c₁ ⊕ c₂ is an encryption of x₃=x₁+x₂.

Cryptosytems enabling to add or to multiply ciphertexts (but not both operations) are called partially homomorphic encryption schemes; examples include the ElGamal cryptosystem (1985) or the Paillier cryptosystem (1999). We say of a scheme that it is “fully” homomorphic when it supports both addition and multiplication of ciphertexts, as any program can be represented as a circuit of additions and multiplications.

The first fully homomorphic scheme was discovered by Craig Gentry in 2009, and introduced the concept of bootstrapping.

Dealing with noise: The bootstrapping trick

Most solutions for fully homomorphic encryption rely on hard lattice problems. Accordingly, the resulting ciphertexts must contain a certain level of noise to guarantee the security of the encryption. This issue however is that computing homomorphically will increase the noise level in the ciphertext. As long as the noise is below a certain threshold, the ciphertext can be decrypted. However, if the noise grows too much, it will overflow on the data itself, rendering decryption impossible.

To prevent this from happening, a special noise-reduction operation called bootstrapping can be applied to the ciphertext, effectively resetting the noise to a nominal level.

In Gentry’s original FHE scheme, bootstrapping is done by homomorphically evaluating the decryption circuit, resulting in another ciphertext that encrypts the same plaintext. Since decryption removes noise, the noise present in a bootstrapped ciphertext is reset to a nominal level (i.e., it only contains the noise coming from the bootstrapping). A possible basic strategy to get a fully homomorphic encryption scheme is therefore to perform a bootstrap operation after each addition or multiplication on ciphertexts using a somewhat homomorphic encryption (SHE).

Bootstrapped or leveled?

Following Gentry’s discovery, successive generations of FHE emerged, aiming mostly at controlling the noise growth in homomorphic computations and/or improving the bootstrapping. Two approaches in particular have emerged:

• Fast bootstrapping (aka “bootstrapped” schemes): FHE schemes are devised with the main goal of reducing as much as possible the computing overhead induced by the bootstrapping. Building on the 3rd generation GSW scheme, the FHEW cryptosystem was designed with greatly improved bootstrapping. Where the multiplication of two ciphertexts in Gentry’s scheme takes 30 minutes, bootstrapping a ciphertext with FHEW runs in about half a second. Bootstrapping in FHEW was later improved to give rise to TFHE with a bootstrapping in a few tens of milliseconds.
• Less noisy operations (aka “leveled” schemes): FHE schemes are parameterized so that the circuit representing a given function can be evaluated homomorphically without resorting to the bootstrap operation. As homomorphic multiplication introduces the most noise, what typically matters is the multiplicative depth (or number of levels) of the circuit being evaluated, that is, the largest sequence of consecutive multiplications. A leveled FHE scheme therefore provisions a noise budget so as to support L levels of multiplications where L is the multiplicative depth of the circuit. Representatives in this family are BFV, BGV, and CKKS.

The selection of an FHE scheme in the first or second family is dictated by the use case: simpler use-cases will be able to build on leveled FHE schemes while more complex ones will make use of bootstrapped FHE schemes. Ideally however, we want to combine both, which is precisely the work we are doing at Zama.

Boolean or arithmetic?

There is another distinction that can be made among the various FHE schemes. Gentry’s initial takes encrypted bits on input and adds or multiplies them. This can be extended in at least two directions.

• Boolean circuits: Addition of bits corresponds to a XOR and multiplication of bits to an AND. Actually any function represented as a boolean circuit consists of a series of binary gates hooked together; it can even only be expressed with the universal NAND gate. Over encrypted data, on input two ciphertexts encrypting bits, a binary gate is evaluated inside a (fast) bootstrap operation. The output ciphertext encrypting the bit result is ‘clean’ — being the output of a bootstrapping, the noise it contains has a fixed level; the process can therefore be iterated. This is the gate bootstrapping as put forward for example in FHEW or TFHE.
• Arithmetic circuits: Instead of working with bits, one can represent inputs with larger integers modulo p for some p>2, and compose through a series of additions and multiplications to form an arithmetic circuit. (Note that boolean arithmetic corresponds to p=2.) This is the approach typically followed by leveled FHE schemes. Other types of input format are also considered when dealing with arithmetic circuits, like real numbers for CKKS; computations in this case are approximate.

Programmable bootstrapping and functional circuits: A new paradigm

To date, the fastest bootstrapping is achieved by TFHE (a few tens of milliseconds). Although originally designed for boolean circuits, TFHE can be extended to support more than booleans as an input format, such as integers.

Furthermore, bootstrapping in TFHE can be programmed to evaluate a univariate function for free, at the same time as the noise is reduced. This is referred to as programmable bootstrapping (PBS), and is currently the most powerful technique available to evaluate homomorphic non-linear functions efficiently, such as activation functions in a neural network.

The PBS operation enables more than the homomorphic evaluation of univariate functions and can be used to compute multivariate functions. For example the max function, max(x, y), can be rewritten as max(x, y) = y +max(0, x - y). There is even a theorem from Kolmogorov (1957) that states that any multivariate function can be expressed as a linear combination of univariate functions.

This yields a new computational paradigm, functional circuits, where a scheme can be fully homomorphic as long as it implemented homomorphic addition and univariate functions. In the case of Zama’s variant of TFHE, the univariate functions are evaluated homomorphically using programmable bootstrapping, while the addition is evaluated in a leveled way.

Programmable bootstrapping, along with the original TFHE features are available as part of Zama’s open source FHE products: TFHE-rs and Concrete.

Application to neural networks

Neural networks it turns out are just a special case of a functional circuit, where activation functions are non-linear univariate functions, taking as input the sum of weighted inputs from previous layers. Computing the activation function has been notoriously hard in FHE, as non-linearities cannot be as precisely represented using simple additions and multiplications versus using programmable bootstrapping.

In a paper we published at CSCML 2021, we showed that programmable bootstrapping enabled evaluating deep neural networks homomorphically, deeper, faster and more precisely that was ever done before. Three neural networks (NN-20, NN-50 and NN-100) with 20, 50 and 100 dense and convolution layers of 92 neurons with ReLu activations were trained on the MNIST dataset, and evaluated on a personal computer (PC) as well as a 3.00 GHz Intel Xeon Platinum 8275CL processor with 96 vCPUs hosted on AWS:

While still early, this shows that FHE is getting ready for prime time, and for being used in cloud applications. We are confident that these benchmarks will improve by a factor of 100–1000x in the next 5 years, making FHE an ubiquitous technology for protecting privacy.

If you’re interested in getting the latest news about homomorphic encryption and what we do at Zama, you can subscribe to our newsletter.

We are hiring! Join Zama and help us safeguard privacy by making the internet encrypted end-to-end. All the info here: jobs.zama.ai

We’re open source — follow Zama’s CONCRETE library on Github here: github.com/zama-ai