Homomorphic encryption
Today I’m gonna talk a bit about a cool buzzword in the crypto world - Homomorphic Encryption. What is it and how does it really work? And maybe more important, why do we want this?
Homomorphism
Homomorphism is defined in a mathematical set such as the result of an operation is mirrored in another set by performing the same operation in that set.
$f:G\rightarrow H$ where $f(xy)=f(x)f(y)$
Oh yes, I finally took the time to integrate LaTeX into Hugo. No more ugly x^2 equations.
In the context of cryptography this means that the result of an operation performed on the ciphertext(G) is mirrored when the same operation is performed on the plaintext(H).
For example, given a ciphertext $\mathit{C}$ and a plaintext $\mathit{P}$, with an operation $\star$ the following holds true in a fully* homomorphic scheme.
$$C'=x\star C$$ $$P'=decrypt(C’)$$ $$P=x\star^{-1} P'$$
where $\mathit{x}$ can be any argument to the operation.
There are basically three types of homomorphic encryption. (1) Partially homomorphic encryption(PHE), this allows one type of operation, (2) Somewhat homomorphic encryption (SWHE) which allows some types of operations and (3) Fully homomorphic encryption (FHE) which allows all operations.
Black magic
This does sound like black magic. Actually RSA is a homomorphic encryption-scheme (PHE). RSA allows unlimited amount of modular multiplications.
$$C = P^{e} \mod n$$ $$C'= C\times x^{e} \mod n$$ $$P'=C'^{d} \mod n$$ $$P=\frac{P’}{x} \mod n$$
Because
$$P'=C'^{d}=(C\times x^{e})^{d}=(P^{e}\times x^{e})^{d}=Px^{ed}=Px \mod n$$
Remember that
$$ed = 1 \mod n$$
This allows one type of operation (modular multiplication) on the ciphertexts. But there actually exists a scheme which allows any operation on the ciphertext, a fully homomorphic encryption-scheme. It’s called Gentry’s FHE.
But when could this be useful?
A obvious application is cloud services. In a traditional cloud service where we hold sesitive encrypted data, the cloud provider owns both the encrypted data and the method to encrypt (and decrypt) the data. Now say an attacker takes control of the cloud service, he owns the encrypted data, and also the means to decrypt it. If we could employ a homomorphic encryption-scheme, the cloud provider can outsource the encryption and decryption methods to the original owner of the data. The cloud provider now only has the encrypted data but can still perform any operation (statisics, sorting, querys etc.) and so on. If an attacker now takes control of the cloud service, he only has control of the encrypted data, which in that form is worthless.
Often when there is talk about homomorphic encryption, some people often mention encrypted databases. Encrypted databases is almost always a bad idea. Matthew Green has an awesome article about this. Looks like with a sufficent amount of querys an attacker can reconstruct parts of the database. Oops!
Conclusion
This is of course super interesting, and is seen like the holy grail of cryptography. Today there exists a fully homomorphic scheme, but it suffers from really serious performance issues. We are probably a long time away from a applicable FHE-scheme.
If you found this interesting. Me and a classmate Johan Näslund, wrote a short paper about homomorphic encryption. You can find it here (Swedish).