Alice and Bob in Cipherspace
A new form of encryption allows you to compute with data you cannot read
The idea of computing with encrypted data was first proposed in 1978 by Ron Rivest, Len Adleman and Michael L. Dertouzos, who were all then at MIT. Just a few months before, Rivest and Adleman, along with Adi Shamir, had introduced the first implementation of a public-key cryptosystem, which came to be known as RSA after their initials. (The RSA paper, by the way, also introduced Alice and Bob in their debut performance as celebrity cryptographers.)
The basic RSA scheme is partially homomorphic: It allows multiplication of ciphertexts but not addition. Rivest, Adleman and Dertouzos pointed out this fact and also mentioned a few other ways to achieve partial “privacy homomorphisms.” They asked whether it would be possible to construct a secure scheme capable of general computation on ciphertexts.
In the next 30 years there were occasional advances on this front. For example, in 2005 Dan Boneh, Eu-Jin Goh and Kobbi Nissim devised a homomorphic system that allowed an unlimited number of additions on the ciphertext, followed by a single multiplication. (Boneh, by the way, was Gentry’s thesis advisor.) In spite of such incremental progress, however, Gentry’s announcement of a fully homomorphic scheme came as a total surprise in 2009.