Alice and Bob in Cipherspace
A new form of encryption allows you to compute with data you cannot read
A Parallel Universe
Over the years, Alice and Bob have gone their separate ways. Alice now works as the research director of a cryptographic software company; Bob has gone into hardware, running a cloud computing service. As they have drifted apart, their security and privacy needs have changed somewhat. When Alice talks to Bob, she still needs to guard against Eve’s snooping. But, in addition, Alice’s company now has proprietary information that she must not disclose to Bob. Complicating her predicament, she wants to use Bob’s computers for tasks that involve the secret data.
Ordinary cryptography is no help in this situation. Alice can encrypt the data when she sends it to Bob, but he can do nothing with it unless he can decrypt it. That is exactly what Alice seeks to avoid. They are at an impasse, which homomorphic encryption is designed to surmount.
Before trying to explain how homomorphic encryption works, I should try to explain the word homomorphic. The Greek roots translate as same shape or same form, and the underlying idea is that of a transformation that has the same effect on two different sets of objects. The concept comes from the esoteric world of abstract algebra, but I can offer a more homely example, where the two sets of objects are the positive real numbers on the one hand and their logarithms on the other. Then multiplication of real numbers and addition of logarithms are homomorphic operations. For any positive real numbers x, y and z, if xy=z, then log(x)+log(y)=log(z). This homomorphism offers two alternative routes to the same destination. If we are given x and y, we can multiply them directly; or we can take their logarithms, then add, and finally take the antilog of the result. In either case, we wind up with z.
Homomorphic cryptography offers a similar pair of pathways. We can do arithmetic directly on the plaintext inputs x and y. Or we can encrypt x and y, apply a series of operations to the ciphertext values, then decrypt the result to arrive at the same final answer. The two routes pass through parallel universes: plainspace and cipherspace.
Arithmetic in plainspace is familiar to everyone. A number is conveniently represented as a sequence of bits (binary digits 0 and 1) and algorithms act on the bits according to rules of logic and arithmetic. Among the many operations on numbers we might consider, it turns out that adding and multiplying are all we really need to do; other computations can be expressed in terms of these primitives.
Doing mathematics in cipherspace is much stranger. Indeed, the task seems all but impossible. Encryption is a process that thoroughly scrambles the bits of a number, whereas algorithms for arithmetic are extremely finicky and give correct results only if all the bits are in the right places. Nevertheless, it can be done.
As a proof of concept, I offer an extremely simple homomorphic cryptosystem. Assume the plaintext consists of integers. To encrypt a number, double it; to decrypt, divide by 2. With this scheme we can do addition on enciphered data as well as a slightly nonstandard version of multiplication. Given plaintext inputs x and y, we can encrypt each of them separately, add the ciphertexts, then decrypt the result. This roundabout calculation gives the correct answer because 2x+2y=2(x+y).
To make multiplication come out right, we have to define the product of ciphertexts as (xy)/2, whereas plaintexts are multiplied by the usual formula xy. With this rule it’s easy to verify that the three-step sequence encrypt-multiply-decrypt yields the same result as simply multiplying the plaintexts. (Fiddling with definitions in order to get the right answer may seem like cheating, but many mathematical objects come with their own idiosyncratic rules for multiplication. Two examples are matrices and complex numbers.)
As cryptosystems go, the doubling scheme is certainly simple, and it’s fully homomorphic. We can do all the arithmetic we want on ciphertexts. On the other hand, the system is not recommended if you actually want to keep secrets. Doubling a number does not thoroughly scramble the bits; it merely shifts them left by one position.
Devising a secure fully homomorphic cryptosystem is much harder. That’s what Gentry accomplished in 2009. Making the system efficient enough for practical applications is yet another challenge, still being addressed.