Back to Blog Lobby
#
What is Homomorphic Encryption?

Privacy Enhancing Technologies (PETs) enable data scientists to perform computations on encrypted data sets in a privacy-preserving manner. There are several PETs, each of which has a different role in data protection and analysis. In this blog, I will provide a brief explanation of one of them, homomorphic encryption (HE), from the cryptographer’s perspective – including a basic explanation of how it works and the difference between partially, leveled and fully homomorphic encryption (FHE).

Homomorphic encryption is a way to perform computations on encrypted data without ever decrypting it first.

An example of a **partially homomorphic encryption scheme **is the well-known RSA encryption scheme. RSA has the property where if you multiply the encryption of 𝑎 and the encryption of 𝑏, you obtain the encryption of 𝑎 ⋅ 𝑏. To see why, we describe the scheme below:

RSA consists of public key (𝑛, 𝑒) and private key 𝑑. Encryptions of messages 𝑎 and 𝑏 are defined below:

𝑐_{𝑎} = 𝑎^{𝑒} (𝑚𝑜𝑑 𝑛)

𝑐_{𝑏} = 𝑏^{𝑒} (𝑚𝑜𝑑 𝑛).

Multiplying the two ciphertexts gives

𝑐_{𝑎𝑏} = 𝑐_{𝑎} ⋅ 𝑐_{𝑏} = (𝑎 ⋅ 𝑏)^{𝑒} (𝑚𝑜𝑑 𝑛).

In practice, RSA is often used with a padding scheme, so the ciphertext 𝑐_{𝑎} will consist of 𝑎^{𝑒} with zeros padded at the end. This destroys the homomorphic properties of the scheme. However, if a user wished, they could use RSA without the padding as a partially homomorphic encryption scheme.

For many applications, being able to simply multiply two ciphertexts is not enough. A **leveled fully homomorphic encryption scheme **is an encryption scheme that satisfies three properties:

- If you add the encryption of 𝑎 and the encryption of 𝑏, you obtain the encryption of 𝑎 + 𝑏.
- If you multiply the encryption of 𝑎 and the encryption of 𝑏, you obtain the encryption of 𝑎 ⋅ 𝑏.
- You can perform a limited number of additions and multiplications on a given ciphertext.

We give an example of a leveled fully homomorphic encryption scheme below. You can find an implementation of the BFV (Brakerski-Fan-Vercauteren) scheme, invented in 2012 and described below, in our open-source library PALISADE.

In order to satisfy both additive and multiplicative properties of leveled fully homomorphic encryption, security properties, and have the ability to decrypt with the secret key, a BFV ciphertext has three components:

- The message 𝑚 – having the message itself hidden in the ciphertext is what allows the scheme to be fully homomorphic. Suppose the encryptions of 𝑎 and 𝑏 are defined to be
𝑐 for some constant Δ. Then_{𝑎}= Δ ⋅ 𝑎

𝑐_{𝑏}= Δ ⋅ 𝑏𝑐 _{𝑎}+ 𝑐_{𝑏}= Δ ⋅ (𝑎 + 𝑏)

and𝑐 So adding the two ciphertexts together gives the encryption of 𝑎 + 𝑏, and multiplying the two ciphertexts together gives us a ciphertext we can modify to obtain the encryption of 𝑎 ⋅ 𝑏. This satisfies the fully homomorphic properties, but is clearly not a secure encryption scheme since anyone can figure out the messages 𝑎 and 𝑏 from the two ciphertexts._{𝑎}⋅ 𝑐_{𝑏}= Δ^{2}⋅ (𝑎 ⋅ 𝑏). - The noise 𝑒 – to make the scheme secure, we add a small noise component.
- The public key 𝑝𝑘 – to make the scheme secure, and in order to decrypt the message with the secret key 𝑠, we need to add the public key to the ciphertext.

Thus, the BFV encryption scheme for a message 𝑚 is defined below:

𝑐_{𝑚} = (Δ ⋅ 𝑚 + 𝑒_{1} + 𝑝𝑘_{1} ⋅ 𝑢, 𝑒_{2} + 𝑝𝑘_{2} ⋅ 𝑢)

where Δ is a constant, 𝑒_{1} and 𝑒_{2} are small noise components, 𝑝𝑘_{1} and 𝑝𝑘_{2} are two parts of the public key, and 𝑢 is a random value.

For decryption, knowing the secret key 𝑠, allows us to add the ciphertext components together in a way that cancels out the public key and leaves the original message with a little noise.

The noise component needs to remain small enough, so that when we divide by the constant Δ and round to the nearest integer, we obtain the original message 𝑚.

Yes. Adding two ciphertexts together increases the noise by a small amount, whereas multiplying two ciphertexts together increases the noise by much more.

If the noise gets too large, the ciphertext will no longer decrypt to the correct message. To ensure this does not happen, if we know the number of additions and multiplications that we wish to perform beforehand, we can choose the encryption parameters in such a way that the noise never gets too large.

**Fully homomorphic encryption (FHE)** satisfies the additional property that you can perform an unlimited number of additions and multiplications.

The first FHE scheme was invented by Craig Gentry in 2009, when he introduced a procedure known as bootstrapping.

If we can prevent the noise from getting too large, we can perform an unlimited number of computations. The easiest way to remove the noise from a ciphertext before the noise gets too large, is to decrypt it. Getting the exact plaintext result and re-encrypting it will refresh the noise back down to be small.

However, we want to perform all our computations without decrypting it in between.

Luckily researchers have found ways to express decryption circuits fully through additions and multiplications, which is something we can do while staying encrypted! Making sure a decryption circuit is bootstrappable is often the most challenging part of designing a fully homomorphic encryption scheme, but research in the past decade has shown that it is possible.

- To run your own C++ code with encrypted data, try using Google’s FHE transpiler, built with our open-source library PALISADE.
- To start using PALISADE on your own or to learn more about homomorphic encryption, check out the PALISADE webinars.
- To learn more about PETs, watch our technical webinar, “Increase Data Insights with Actionable Outcomes.”