Homomorphic Encryption : Part 1 posted July 2015

I'm reading stuff about HE (Homomorphic Encryption) and so why not share what I find? Hopefuly there will be more than one post on the subject, and they won't be too long, and they will make others learn something new

So what is Homomorphic Encryption?

Well let's start at the beginning shall we? It all began in 1977 when RSA was invented. If you recall, to encrypt with RSA you take your message/number \(m\) and raise it to the power of the public exponent \(e\) modulo a product of primes \(N\) like so:

\[ c = m^e \pmod{N} \]

An incredible property of textbook RSA is the fact that the scheme is malleable. If you have a ciphertext \(c\) but don't know what number \(m\) it's decrypting to, you can modify that ciphertext \(c\) so that it would decrypt to \(3m\) or \(9999m\) or more generally \(x \cdot m\). Just take your number \(x < N \) and encrypt it, then multiply that to your ciphertext like so:

\[ x^e \cdot c \pmod{N} \]

And notice that beneath the encryption, this is equal to

\[ x^e \cdot m^e \pmod{N} \]

That is the same as

\[ (x \cdot m)^e \pmod{N} \]

and will obviously decrypt as \( x \cdot m \). Tell me if I'm going too slow =)

This is called Homomorphic Encryption, which you might not want as a property when using RSA and that's why you should never use RSA without a padding system. The state of the art being OAEP.

This made Rivest and his friends raise the question, a year later in 1978, can this property be extended so that any kind of circuit could be computed on encrypted data? (R. Rivest, L. Adleman, and M. Dertouzos. On data banks and privacy homomorphisms. In Foundations of Secure Computation)

Fully Homomorphic Encryption

The applications thought were mostly "data manipulation" where you would want someone to manage/operate on your data without seeing it. Think banks, search engines, the cloud.

A bunch of other cryptosystem that provided homomorphic properties came to life after that. For example in 1999 the Paillier cryptosystem, which unlike RSA provides additive homomorphic encryption (RSA provides multiplicative homomorphic encryption).

The open problem was still out there. Could you create a cryptosystem that would provide enough homomorphic properties, that combined could compute any kind of circuits. A Fully Homomorphic Cryptosystem.

Any circuit can be simplified to these simple instructions: AND, OR and NOT, which would only need a cryptosystem to have addition, subtraction and multiplication to be able to emulate these instructions.

Modulo 2 would be enough, look, if \( x \in \mathbb{Z}_2 \) (the set of 0 and 1) then:

• \( \text{AND}(x,y) = xy \)
• \( \text{OR}(x,y) = 1 - (1-x)(1-y) \)
• \( \text{NOT}(x) = 1 - x \)

With these properties combined you could then compute any circuit on encrypted data (think of a function, like AES() or select all my data that starts with the letter A, etc...).

So, just a recap so that we're on the same page. With a FHE Alice could send \( c = E(m) \) the encryption of her message \( m \) to Bob, and bob could compute the function \( f \) on the encrypted data so that it would decrypt to a function \(f\) on the plaintext:

\[ D(f(c)) = f(m) \]

Note that in reality, we can't really compute \( f \) on the ciphertext directly, what we do is that typically a Homomorphic Encryption scheme is defined with a function called Eval (for Evaluate) which we would use like that:

\[ D(\text{Eval}(f, c)) = f(m) \]

In 2009, Dan Boneh's doctorate student Craig Gentry finished his thesis, unveilling the first FHE (Fully Homomorphic Encryption):

In a presentation to my fellow Ph.D. admits four years ago, Dan highlighted fully homo- morphic encryption as an interesting open problem and guaranteed an immediate diploma to anyone who solved it. Perhaps I took him too literally.

Craig Gentry, Fully homomorphic encryption using ideal lattices, 2009

His thesis of 200 pages was later resumed in a 10 pages article for STOC 2009: Fully Homomorphic Encryption Using Ideal Lattices.

A bit later Gentry et al simplified that scheme using only hard problems on integers instead of lattices, this was explained as well in another article for CACM here: Computing Arbitrary Functions of Encrypted Data

In the next post we'll see how that FHE works!