Homomorphic Encryption

Homomorphic encryption is a cryptographic method that allows mathematical operations on data to be carried out on cipher text, instead of on the actual data itself. The cipher text is an encrypted version of the input data (also called plain text). It is operated on and then decrypted to obtain the desired output. The critical property of homomorphic encryption is that the same output should be obtained from decrypting the operated cipher text as from simply operating on the initial plain text.

The following graphic explains how homomorphism is used in encryption. The process begins with some plain text message, $m$. It could be the name of someone in a computer system, "jane doe". The goal is to perform some function $f$ on it, like capitalizing the name. That's possible, but it would be safer to encrypt the message using $enc$ before performing any functions on it so the person performing the function never learns Jane's name. So the message is encrypted to some cipher text 163726. Then, it is evaluated, or transformed, into another value using some other function, $f(x) = x + 127$, for example. The output, 163853, is another completely encrypted message. This message can then be decrypted to "Jane Doe".

Homomorphism and encryption

Current homomorphic encryption exists in partial and full forms. Partially homomorphic systems only allow certain operations on encrypted data, typically multiplication or division, and have existed for many years. Fully homomorphic systems, which allow all operations on encrypted data, remained an open problem in cryptography for 30 years, but they were finally solved in 2009. It is typically desirable because it allows a system to chain together multiple operations that are all performed on encrypted data so as not to expose unencrypted data.

Homomorphic encryption was first suggested in the 1970s. The concept was that it should be possible to perform mathematical operations on encrypted data without having to decrypt any part of it. This clearly had huge implications for modern computing.

In a typical homomorphic crypto-system, there will be some information that will be public and some information that will be private. For example, in the graphic in the introduction, the information needed to perform the $enc$ function might be public. That way, anyone can encrypt a message. It is much more important that the information needed to perform the $decrypt$ function is private. That way, no attacker can steal the evaluated encryption $enc(f(m))$ and decrypt it for themselves. This is a foundation of RSA encryption.

In cryptography, it is assumed that there is some sort of communication going on between two people. Let's call them Alice and Bob. Maybe Alice wants to give Bob a suitcase full of money to count and give back to her. Alice hands Bob the suitcase, and Bob asks for the key to open it. Alice doesn't want to give him the key because she's not very trusting. Bob, however, doesn't know how to count the money if Alice won't let him open the box. So, the couple have two options:

1. Alice could give Bob the key. This would work. However, there is also an attacker out there who wants to steal the money, Eve. She could be impersonating Bob, or she could steal both the suitcase and key from Bob later.

2. Devise a new kind of lock, even better than a suitcase that needs a key. This lock won't let anyone who isn't Alice get to the money or even know how much money is in there. But it will allow anyone with the right permission to count it. This is the concept behind homomorphic encryption and why it's so powerful.

Homomorphic encryption is malleable by design. A malleable crypto-system is one in which anyone can intercept a cipher text, transform it into another cipher text, and then decrypt that into a plain text that makes sense. Malleability is generally considered undesirable in a crypto-system. Imagine you're trying to send the message "I love you" to your friend using encryption. You encrypt it and send it off. But, it is intercepted by a hacker on the way. All they see is some cipher text, but they can change that cipher text to something that will decrypt to "I hate you" when your friend tries to decrypt it. That is why malleability to not usually wanted.

A malleable crypto-system

However, homomorphic systems should be malleable. Maybe You want to build a system that simply adds exclamation marks to whatever you send your friend. But, you don't want the system to know what you're sending your friend, that's a secret. You encrypt your message and send it along to your system. Your system only sees the cipher text, so it doesn't know what you're saying, but it can still transform the cipher text. It transforms the cipher in a text that will decrypt to the same input message, plus a few exclamation marks. So, now it looks like this.

Another malleable crypto-system

Malleable systems allow for multiple parties, especially in cloud-based environments, to operate on data without ever exposing it.

Homomorphic encryption has seen revitalization in recent years, especially due to cloud computing. Resources for computation are so cheap that many system outsource their computation to companies like Amazon or Microsoft and their huge data centers. However, those systems don't want to expose that data for attack. So, they encrypt the data, send it to a data center, it is operated on, and then it is send back to the original system for decryption.

Privacy is very important in today's computing environment. Private information that is used by various systems often uses homomorphic encryption if that data needs to stay encrypted. E-voting, for example, might want to use homomorphic encryption to protect voting privacy.

E-cash systems might also use homomorphic encryption. If you send money to a friend, you might not want the system to know how much money you are sending. The system could retrieve both you and your friend's encrypted data, add them together, and then send them back to your friend.

Finally, most of these applications have concerned ways of protecting this like messages and data. However, homomorphic encryption can also be used to protect algorithms and code. The probable use case of such a system would need to protect both the incoming data and the algorithm that processes it. Fully homomorphic encryption techniques are still a hot research topic, so this application may not be as far off as once thought.

RSA Encryption

RSA encryption has multiplicative homomorphism. It works by first selecting two large primes, $p$ and $q$, and sets $n = p \cdot q$. It also choses $a$ and $b$ such that

$$a \cdot b \equiv 1 \mod \phi(n) .$$

$p$, $q$, and $a$ are private, while $b$ and $n$ are public knowledge. The encrypt and decrypt functions are then

$$Enc(x) = x^b \mod n ,$$ $$Dec(x) = y^a \mod n .$$

To prove the homomorphism, suppose that $x_1$ and $x_2$ and plain text data. Then,

$$Enc(x_1) \cdot Enc(x_2) = x_1^b \cdot x_2^b \textrm{ mod } n = {(x_1 \cdot x_2)}^b \textrm{ mod } n = Enc(x_1 \cdot x_2) .$$

Unfortunately, basic RSA encryption like this is not secure. It is not randomized, so an attacker can check for equality. To do so, they can launch input many likely plain text inputs and observe the decrypted output. Once, they find an output that matches something the see in the system, they know the secret input data.

ElGamal^[1]

The ElGamal crypto-system is also multiplicative in its homomorphism. It works picking $\alpha \ \epsilon \ Z_p^*$ where $p$ is a prime and $\alpha$ is a generator of $Z_p^*$. Then, $a$ and $\beta$ are chosen such that $\beta \equiv \alpha^a$. Now, $p$, $\alpha$ and $\beta$ are public while $a$ is private. Finally $r \ \epsilon \ Z_{p-1}$ is a secret random number. Then,

$$Enc(x, r) = (\alpha^r \textrm{ mod } p, x \cdot \beta^r \textrm{ mod } p) .$$

To prove the homomorphism, we again assume that $x_1$ and $x_2$ and plain text data.

$$Enc(x_1, r_1) \cdot Enc(x_2, r_1) = (\alpha^{r_1} \textrm{ mod } p, x_1 \cdot \beta^{r_1} \textrm{ mod } p) \cdot (\alpha^{r_2} \textrm{ mod } p, x_2 \cdot \beta^{r_2} \textrm{ mod } p) ,$$ $$= (\alpha^{r_1} \cdot \alpha^{r_2} \textrm{ mod } p, (x_1 \cdot x_2) \beta^{x_1}\beta^{x_2} \textrm{ mod } p ,)$$ $$= (\alpha^{r_1 + r_2} \textrm{ mod } p, (x_1 \cdot x_2) \beta^{x_1 + x_2} \textrm{ mod } p ,)$$ $$= Enc(x_1 \cdot x_2, r_1 + r_2) .$$

Paillier

Paillier has the property of additive homomorphism. This makes it very useful for application such as e-voting, as shown below. It first picks two large primes, $p$ and $q$, and sets $n = pq$. $\lambda$ is the Carmichael function. That is,

$$\lambda(n) = \textrm{lcm}(p-1, q-1)$$

where lcm is a function that returns the least common multiple of its two inputs. It picks a random $g \ \epsilon \ Z_{n^2}^*$ such that $L(g^\lambda \textrm{ mod } n^2)$ is invertible modulo $n$. Note that the generator $Z_{n^2}^*$ is the set of all numbers smaller than $n^2$ that are relatively prime to $n^2$. For a number $g$ to be relatively prime to $n^2$, the gcd of g and n^2 must equal 1.

$L$ is a function such that

$$L(u) = \frac{u-1}{n} .$$

$n$ and $g$ and public. $p$ and $q$ are private. For plaintext $x$ and resulting cipher text $y$, we select a random $r \ \epsilon \ Z_n^*$. Now we have,

$$Enc(x, r) = g^x \cdot r^n \textrm{ mod } n^2 ,$$ $$Dec(y) = \frac{L(y^\lambda \textrm{ mod } n^2)}{L(g^\lambda \textrm{ mod } n^2)} \textrm{ mod } n .$$

This example will take you through the use of Paillier's crypto-system. Recall that Paillier's has additive homomorphism which makes it an excellent choice to add the results of an election.

Paillier's crypto-system has important applications in E-voting. Let's say that we have three candidates, Alice, Bob, and Charlie. We can assign a certain number of bits to each candidate during a vote. 010000 for Alice, 000100 for Bob, and 000001 for Charlie. Let's say we have 6 people voting and the results are as follows:

We'll let $p = 5$ and $q = 7$, so $n = 35$ and $n^2 = 1225$. $\lambda = 12$ and $g$ is randomly chosen to be 141.

Taking the first vote, $x_1 = 1$, $r$ is randomly chosen to be 3. Calculate the encryption value for $x_1$ with $r = 3$.

Show Answer

$$Enc(1, 3) = 141^1 \cdot 3^{35} = 1062 \textrm{ mod } 1225 .$$

Below is a table of votes, with their associated encrypted value. Remember that for each vote, a random $r$ was chosen.

Now we need to sum the votes (since this is an election). Recall that Paillier encryption has additive homomorphism, so this is a perfectly fine operation to make. Additive homomorphism means that the product of two cipher texts can be decrypted to find the addition of their plain texts. We take the product of all the votes modulo our $n^2$.

$$359 \cdot 173 \cdot 486 \cdot 1088 \cdot 541 \cdot 163 = 983 \textrm{ mod } 1225 .$$

Now, decryption is performed.

$$L(y^\lambda \textrm{ mod } n^2) = L(983^{12} \textrm{ mod } 1225) = \frac{36 - 1}{35} = 1 ,$$ $$L(g^\lambda \textrm{ mod } n^2) = L(141^{12} \textrm{ mod } 1225) = \frac{456 - 1}{35} = 13 ,$$ $$dec(y) = (L(y^\lambda \textrm{ mod } n^2))(L(g^\lambda \textrm{ mod } n^2))^-1 \textrm{ mod } n ,$$ $$= 1 \cdot 13^-1 \textrm{ mod } 35 ,$$ $$= 27 .$$

27, when converted to binary, is 011011. Looking back at this problem was set up, Alice had the first two bits assigned to her. So, she received 01, or 1, vote. Bob had the second two bits assigned to him, so he received 10, or 2, votes. Charlie had the last pair, so he received 11, or 3 votes. Hence we know who won the election. The engineer will always set the problem up so that there is not possibility of arriving at an incorrect value. In practice, it takes far more than two bits per option to make this method work.

Fully homomorphic systems are homomorphic systems in which any kind of mathematical operation can be performed on the cipher text. Fully homomorphic systems do exist today, and their optimizations since 2009 have made them practical for some applications. Craig Gentry was the first to suggest that they could be theoretically possible. He was able to create a system that was homomorphic in two ways, and those two ways allowed full homomorphism.

Gentry uses the analogy of a jewelry shop owner in his thesis to describe why fully homomorphic systems should be, and are, possible. Imagine that Alice is a jewelery store owner. She has employees that assemble products from raw materials like diamonds and gold. But, she's worried about the possibility of theft. So, she designs boxes that have gloves attached to them. Employees can stick their hands into the box to assemble the products, but they cannot take anything out of the box because only Alice has the key. So, Alice's employees can do operations on the secure data (the jewelry) without ever having the possibility of taking that secure data out.

Gentry's system incorporates an amount of noise into the cryptographic process. Each successive encryption introduces more noise into the system, which is why Gentry's initial design is impractical (though it was later improved upon). It is impractical to use noise because eventually the system needs to be restarted because the added noise makes the entire system much slower. This system relies on ideal Lattice Based Cryptography to simplify much of the system's design.

1. Lange, . An Overview of Homomorphic Encryption. Retrieved July 11, 2016, from https://www.cs.rit.edu/~arl9577/crypto/alange-presentation.pdf