Homomorphic encryption
Makes it possible to do calculations directly on encrypted data, without ever decrypting it.
num_A = encrypt(9)
num_B = encrypt(1)
res = num_A + num_B
res_decrypted = decrypt(res)
assert(res_decrypted == decrypt(num_B) + decrypt(num_B))
How is it possible? (simple example):
The whole point can be imagined in the context of the cloud and, more generally, of renting machine power. Let's imagine a service that lets you do calculations very fast and on a large amount of data. It is practical but the computer necessarily has access to the data it is adding/dividing etc... And so we lose confidentiality.
But if we give the computer encrypted data, it gives us the result and we have to decrypt it afterwards, we avoid this problem. This applies to a lot of possibilities since once we can calculate, it is almost the same as sending it a program to execute without it being able to really understand how it works (so it is also closely related to the topic of indistinguishability obfuscation, see the corresponding article).
Types of homomorphic encryption
Partially homomorphic (PHE)
Allows only one operation: addition or multiplication
RSA (allows multiplication):
from math import gcd
"""
cf Introduction to cryptography
Choose two prime numbers p and q, calculate N (p * q) and phi(N)
Find e such that e is coprime with phi(N); e and phi(N)
Find d such as : (e * d) % phi(N) = 1
"""
p, q = 61, 53
n = p * q
phi = (p - 1) * (q - 1)
e = 17
assert gcd(e, phi) == 1
d = pow(e, -1, phi)
def enc(m):
return pow(m, e, n)
def dec(c):
return pow(c, d, n)
c = enc(7) * enc(6) % n
print(dec(c)) # should print 42 (7*6)
Paillier (allows addition):
from math import gcd, lcm
"""
Choose two prime numbers p and q, calculate N (p * q) and lambda = lcm(p - 1, q - 1)
Take g = N + 1 and mu = lambda^-1 mod N
Encrypt: c = g^m * r^N mod N^2, with r random and coprime with N
Decrypt: m = L(c^lambda mod N^2) * mu mod N, with L(x) = (x - 1) / N
"""
p, q = 11, 13
n = p * q
n2 = n * n
g = n + 1
lam = lcm(p - 1, q - 1)
mu = pow(lam, -1, n)
def enc(m, r):
return pow(g, m, n2) * pow(r, n, n2) % n2
def dec(c):
return (pow(c, lam, n2) - 1) // n * mu % n
c = enc(20, 5) * enc(22, 7) % n2
print(dec(c)) # should print 42 (20+22)
Why does RSA allow multiplication and Paillier addition?
RSA encrypts by raising to a power:
And a power naturally distributes over the product:
(a*b)^e = a^e * b^e
(5*6)^8 = 5^8 * 6^8
30^8 = 390625 * 1679616
656100000000 = 390625 * 1679616
656100000000 = 656100000000
On the other hand:
So adding two RSA ciphertexts gives nothing usable.Paillier encrypts by putting the message in the exponent, and:
The message is "hidden in an exponent", and the only thing we know how to do with exponents is to add them.The exponent is the small number at the top in a power: it shows how many times we multiply the base by itself.
Multiplying two powers with the same base is the same as putting the multiplications one after the other, so adding the exponents :
Do we have to remove modern security measures for it to work?
For RSA, yes. Basic RSA is deterministic and malleable, which gives the homomorphic property. Real implementations never use RSA as it is. They apply a padding (OAEP, PKCS#1 v1.5) that adds randomness and a structure that is checked at decryption. This padding breaks the homomorphic property.
Paillier no. It is designed from the start to be homomorphic. It natively includes randomness and is proven secure in the "IND-CPA" standard (Indistinguishability under Chosen-Plaintext Attack, there is no risk of finding the key by analyzing the original text and its encrypted result).
This randomness does not get in the way of the homomorphic property, because it lives in a part of the ciphertext that decryption cancels. And the reason why this is possible is that this randomness does not accumulate, unlike other modern encryption schemes where the randomness adds up (learning with errors), which creates a noise problem. We will talk about it again later in the article.
What we lose, on the other hand, whatever the scheme, is integrity. Modern encryption uses MAC (Message Authentication Code) mechanisms to avoid for example bit flipping attacks, that is to say modifying the encrypted content to manipulate the future plaintext (see my article "Introduction to cryptography"). Homomorphic encryption and these mechanisms are incompatible and useless, since the whole point is precisely to be able to modify the encrypted data.
Somewhat homomorphic (SHE)
With SHE encryption we can do several operations but only a limited number because of the noise problem.
The two main SHE schemes are BGV (Brakerski-Gentry-Vaikuntanathan, 2011) and BFV (Brakerski/Fan-Vercauteren, 2012). They are based on the same mathematical problem (RLWE, Ring Learning With Errors, we come back to it later) and both work with integers "modulo t", that is to say numbers that go around in a loop like the hours of a clock.
The whole difference between BGV and BFV is about where we put the message compared to the noise, to be able to separate them at decryption.
Let's take a simplified example in base 10 with t = 10, a message m = 7 and a noise of 23:
BFV: the message is stored in the high digits, the noise in the low digits
7 × 1000 + 23 = 7023
we round to the nearest thousand: 7000 m = 7
BGV: the message is stored in the low digits, the noise is multiplied by t
7 + (10 × 23) = 237
we keep the last digit (remainder of the division by 10): m = 7
As long as the noise stays small enough to not overflow onto the message, we get the right result back. The problem is that after a while it overflows, and decryption gives nonsense.
This is where the two approaches differ:
-
BFV: lets the noise grow without doing anything, but since the message is "at the top" and the noise "at the bottom", it has a big margin before the two meet.
-
BGV: after each multiplication it "shrinks" the ciphertext (modulus switching). The noise becomes smaller in proportion, and we can chain more operations. The downside is that each shrinking uses a "level", and we have to manage these levels, in particular know in advance how many multiplications we are going to do, make sure that two ciphertexts are at the same level before combining them etc...
In practice, modern libraries (like OpenFHE used below) hide a big part of this complexity, and the performance of both is often close. The choice is mostly made depending on the type of calculation : BFV for simplicity, BGV when we want to push the number of multiplications.
BGV:
# src = https://github.com/openfheorg/openfhe-python/tree/main/examples/pke
from openfhe import CCParamsBGVRNS, GenCryptoContext, PKESchemeFeature
params = CCParamsBGVRNS()
params.SetPlaintextModulus(65537)
params.SetMultiplicativeDepth(2)
cc = GenCryptoContext(params)
cc.Enable(PKESchemeFeature.PKE)
cc.Enable(PKESchemeFeature.KEYSWITCH)
cc.Enable(PKESchemeFeature.LEVELEDSHE)
keys = cc.KeyGen()
cc.EvalMultKeyGen(keys.secretKey)
def enc(m):
return cc.Encrypt(keys.publicKey, cc.MakePackedPlaintext([m]))
def dec(c):
pt = cc.Decrypt(c, keys.secretKey)
pt.SetLength(1)
return pt.GetPackedValue()[0]
c = cc.EvalMult(cc.EvalAdd(enc(4), enc(3)), enc(6))
print(dec(c)) # should print 42 ((4+3)*6)
Learning with errors
Learning With Errors is a mathematical problem proposed by Oded Regev. It is used by a huge number of modern homomorphic encryption schemes, but also in post-quantum cryptography.
To understand it, let's start from a problem : what is the value of s1 and s2 (where these two values are conceptually secrets)?
2*(2 * s1) + 2*(1 * s2) = 2*11
2*(2 * s1) + 2*(1 * s2) = 22
(4 * s1) + (3 * s2) = 27
- 2*(2 * s1) - 2*(1 * s2) - 22
----------------------------------------
0*s1 1*s2 = 5 (27 - 22)
(2 * s1) + (1 * 5) = 11-5 = 6
6 /2 = 3
s1 = 3
s2 = 5
Now, let's add a small random error to the result, of +1 or -1:
If we solve this system like before, we find s1 = 5 and s2 = 2. Completely wrong, even though the errors in the result were tiny. This is the whole principle of LWE: a very small error is enough to make the secrets (s1 s2) impossible to find. With hundreds of unknowns and calculations whose result is "modulo" (which prevents guessing their order of magnitude), we don't know any efficient method to find the secret, even with a quantum computer.
How do we use it to encrypt ? Conceptually:
With the key, we can recalculate and remove the random part, and we get rid of the error by rounding.
And this is where the famous noise problem appears. If we add two ciphertexts, we add the messages but also the errors (it is worse with multiplication).
The "R" of RLWE (Ring LWE), used by BGV and BFV, is an optimized variant that, instead of working with single numbers, works with polynomials (lists of numbers whose value is defined by their position in this list). This makes it possible to store several values in a single ciphertext to process them all at the same time:
Example where we want to store 3, 5, 2 in P and add them with Q:
P(x) = 3 + 5x + 2x²
Q(x) = 1 + 1x + 4x
P + Q = 4 + 6x + 6x²
A single homomorphic addition did three additions: 3+1, 5+1 and 2+4.
Fully Homomorphic Encryption (FHE)
Fully homomorphic encryption lets us do as many additions and multiplications as we want (and that is enough to run any program because the computer only handles 0 and 1, and that is enough to create all the logic gates).
For 30 years, nobody knew if it was possible. It was Craig Gentry who found the solution in 2009, in a PhD thesis, with an idea that unlocked everything:
Bootstrapping
The idea is to do the decryption in a homomorphic way. Decryption is just a calculation (a few additions and multiplications with the key). So:
-
We give the server the secret key, but encrypted. It cannot get anything from it.
-
When a ciphertext becomes too noisy, the server runs the decryption algorithm on it, in a homomorphic way, using the encrypted key.
-
Result : the same message, still encrypted, but with the noise put back to a low level. Because the old noise stops being noise. It becomes encrypted data, and the decryption done in a homomorphic way erases it, like any rounding.
One condition for it to work: the decryption calculation itself must use less "noise budget" than what we have, otherwise we gain nothing.
The price to pay is performance. The first implementation (Gentry and Halevi, 2011) took about 30 minutes for a single bootstrapping.
The main FHE schemes
We don't use Gentry's original scheme anymore, because it is slower than some modern versions based on RLWE:
-
BGV and BFV + bootstrapping: They work on integers, and their bootstrapping is expensive.
-
CKKS (Cheon-Kim-Kim-Song, 2017): the idea is to work with decimal numbers and to accept an approximate result. The noise is no longer an enemy to remove, it is treated as a rounding error (like when a calculator shows 0.30000004 instead of 0.3). Ideal for calculations where a result exact to the nearest billionth doesn't matter.
-
TFHE (Chillotti-Gama-Georgieva-Izabachène, 2016): it encrypts the bits one by one (or small integers) and does a bootstrapping after each logic gate. Its bootstrapping is so fast that it becomes viable.
Example with TFHE
OpenFHE also offers an implementation of TFHE:
# src = https://github.com/openfheorg/openfhe-python/tree/main/examples/binfhe
import time
from openfhe import BinFHEContext, BINFHE_PARAMSET, BINFHE_METHOD, BINGATE
cc = BinFHEContext()
cc.GenerateBinFHEContext(BINFHE_PARAMSET.STD128, BINFHE_METHOD.GINX)
sk = cc.KeyGen()
# bootstrapping key (the encrypted key)
cc.BTKeyGen(sk)
def enc(n, bits=8):
return [cc.Encrypt(sk, (n >> i) & 1) for i in range(bits)]
def dec(cts):
return sum(cc.Decrypt(sk, c) << i for i, c in enumerate(cts))
def add(a, b):
out, carry = [], cc.Encrypt(sk, 0)
for x, y in zip(a, b):
x_xor_y = cc.EvalBinGate(BINGATE.XOR, x, y)
out.append(cc.EvalBinGate(BINGATE.XOR, x_xor_y, carry))
carry = cc.EvalBinGate(BINGATE.OR,
cc.EvalBinGate(BINGATE.AND, x, y),
cc.EvalBinGate(BINGATE.AND, carry, x_xor_y))
return out
start = time.time()
total = enc(0)
for i in range(1, 11):
total = add(total, enc(i))
# should print 55
print(dec(total), f"({time.time() - start:.1f}s)")
More than a minute and a half for an addition that a processor does in a nanosecond : this clearly shows both the power of FHE (the server ran a real program without ever seeing the numbers) and its performance limits.
The link with indistinguishability obfuscation
Homomorphic encryption hides the values, but not the calculation: the server doesn't see the data, but it knows which program it is running. The ideal would be to give it a program without it knowing either the values it handles or the calculation itself. This is the goal of indistinguishability obfuscation.
While calculating with unknown values and giving a good result is possible and proven, running a program without being able in the end to "distinguish" the operations that the CPU does seems impossible in theory. But actually, just like classic encryption, in the end obfuscation consists of slowing down the "decryption/understanding" operation of the program to a point where it is mathematically too expensive to succeed (see the article on the topic).