What is Homomorphic Encryption?

Saroja Erabelli|
Share on twitter
Share on linkedin

What is Homomorphic Encryption?

Saroja Erabelli|
Share on facebook
Share on twitter
Share on linkedin

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). 

What is homomorphic encryption?

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

Example – RSA encryption

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

𝑐𝑎𝑏 = 𝑐𝑎 ⋅ 𝑐𝑏 = (𝑎 ⋅ 𝑏)𝑒 (𝑚𝑜𝑑 𝑛).

Does this mean that RSA encryptions in the real world are homomorphic?

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.

What is leveled fully homomorphic encryption?

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:

  1. If you add the encryption of 𝑎 and the encryption of 𝑏, you obtain the encryption of 𝑎 + 𝑏.
  2. If you multiply the encryption of 𝑎 and the encryption of 𝑏, you obtain the encryption of 𝑎 ⋅ 𝑏.
  3. 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.

Example – BFV encryption

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:

  1. 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
    𝑐𝑎  ⋅ 𝑐𝑏 = Δ2 ⋅ (𝑎 ⋅ 𝑏).
    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.
  3. 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.

How can I decrypt if there is a noise component?

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 𝑚.

Do adding and multiplying ciphertexts together increase the noise?

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

What happens if the noise gets too large?

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.

What is fully homomorphic encryption?

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.

Bootstrapping – how do we reduce the noise of a ciphertext?

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.

How can I start using homomorphic encryption?

Sign up for more knowledge and insights from our experts
Duality Makes CB Insights’ AI 100 List for 2022 >> Read More