COMPUTING SCIENCE

# Alice and Bob in Cipherspace

A new form of encryption allows you to compute with data you cannot read

# Putting Code to Work

Lauter, Naehrig and Vaikuntanathan also discuss some of the ways we might use homomorphic computing. Ensuring the privacy of online medical records is one application. The patient would grant doctors access to selected records by sharing a secret key.

Wall Street is another potential customer for homomorphic services. The “quants” who base investment decisions on computational analysis have a strong proprietary interest not only in their data but also in their algorithms. With FHE both can be protected by the same mechanism.

A third idea is to build a cryptographic privacy fence between online advertisers and consumers. Advertisers, eager to reach individuals with specific interests or habits, gather and cross-index data on people’s activities on the Internet and elsewhere. A service based on homomorphic encryption could match ads to targeted consumers while ensuring that advertisers learn nothing about the people selected.

When I asked Vaikuntanathan what application he thought might be deployed first, he had another suggestion: spam filtering. If you publish a public key and invite correspondents to send you encrypted email, a spammer can take advantage of the key to encrypt advertisements and the other effluvia that fills our mailboxes. Spam-filtering services cannot read and reject the encrypted spam unless you are willing to share your decryption key; homomorphic encryption could solve that problem.

My own fantasy application is an offshore bank called the Homomorphic Trust Company. The online interface might look much the same as any other bank’s, with the usual cryptographic safeguards against intruders. But at this bank, even the bankers could not know the details of your transactions. I think Alice might be interested; she could get rid of that suitcase full of uncountable cash.

# Bibliography

- Boneh, D., E.-J. Goh and K. Nissim. 2005. Evaluating 2-DNF formulas on ciphertexts. In
*Proceedings of Theory of Cryptography*, pp. 325–341. - Brakerski, Z., C. Gentry and V. Vaikuntanathan. 2011. (Leveled) fully homomorphic encryption without bootstrapping. In
*Proceedings of the Third Innovations in Theoretical Computer Science Conference*, pp. 309–325. - Brakerski, Z., and V. Vaikuntanathan. 2011. Fully homomorphic encryption from ring-LWE and security for key dependent messages. In
*Proceedings of the 31st Annual Cryptology Conference*, pp. 505–524. - Coron, J., D. Naccache and M. Tibouchi. 2011. Public key compression and modulus switching for fully homomorphic encryption over the integers. In
*Proceedings of Eurocrypt 2012*, pp. 446–464. - Gentry, C. 2009. A fully homomorphic encryption scheme. Ph.D. dissertation. Stanford University. Available at http://crypto.stanford.edu/craig.
- Gentry, C. 2009. Fully homomorphic encryption using ideal lattices. In
*Proceedings of the 41st ACM Symposium on Theory of Computing*, pp. 169–178. - Gentry, C. 2010. Computing arbitrary functions of encrypted data.
*Communications of the ACM*53(3):97–105. - Gentry, C., and S. Halevi. 2011. Implementing Gentry’s fully-homomorphic encryption scheme. In
*Proceedings of Eurocrypt 2011*, pp. 129–148. - Gentry, C., S. Halevi and N. P. Smart. 2012. Fully homomorphic encryption with polylog overhead. In
*Proceedings of Eurocrypt 2012*, pp. 465–482. - Goldwasser, S., and S. Micali. 1982. Probabilistic encryption and how to play mental poker keeping secret all partial information. In
*Proceedings of the 14th ACM Symposium on Theory of Computing*, pp. 365–377. - Gordon, J. 1984. The story of Alice and Bob. http://www.johngordonsweb.co.uk/concept/alicebob.html.
- Lauter, K., M. Naehrig and V. Vaikuntanathan. 2011. Can homomorphic encryption be practical? In
*Proceedings of the Third ACM Workshop on Cloud Computing Security*, pp. 113–124. - Rivest, R. L., L. Adleman and M. L. Dertouzos. 1978. On data banks and privacy homomorphisms. In
*Foundations of Secure Computation*(New York: Academic Press), pp. 169–180. - Smart, N. P., and F. Vercauteren. 2010. Fully homomorphic encryption with relatively small key and ciphertext sizes. In
*Proceedings of the Conference on Practice and Theory in Public Key Cryptography*, pp. 420–443. - van Dijk, M., C. Gentry, S. Halevi and V. Vaikuntanathan. 2010. Fully homomorphic encryption over the integers. In
*Proceedings of Eurocrypt 2009*, pp. 24–43.

EMAIL TO A FRIEND :

**Of Possible Interest**

**Engineering**: Traffic Signals, Dilemma Zones, and Red-Light Cameras

**Perspective**: Taking the Long View on Sexism in Science

**Computing Science**: Computer Vision and Computer Hallucinations

**Other Related Links**