COMPUTING SCIENCE

# Alice and Bob in Cipherspace

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

# Three’s a Crowd

In the early days of their relationship, Alice and Bob kept no secrets from each other; it was the rest of the world they wanted to shut out. Their main problem was how to communicate privately over a public channel, where nosy third parties—such as Eve the eavesdropper—might be listening in. To solve this problem, Alice and Bob devised a variety of cryptographic schemes. Before sending a message to Bob, Alice would encrypt it with a secret key, turning plaintext into ciphertext; even if Eve intercepted the ciphertext, she could make no sense of it. But Bob had the decryption key, so he could recover the plaintext.

For some cryptosystems, Alice and Bob must each hold a copy of the same key, which both encrypts and decrypts. But then they face the thorny issue of how to transmit the key itself, without having it fall into Eve’s hands. A particularly clever solution, called public-key cryptography, splits the key into two parts. Alice and Bob each publish a public encryption key, which allows anyone to send them an encrypted message. But they keep secret the corresponding decryption keys, so that only they can read the messages they receive.

Another innovation that helped Alice and Bob keep their private conversations out of the tabloid press was probabilistic cryptography, introduced in the early 1980s by Shafi Goldwasser and Silvio Micali of MIT. Earlier systems were deterministic: The same plaintext always produced the same ciphertext. But determinism is dangerous in public-key cryptography. Eve can try guessing the content of a message; then she encrypts the guess with the public key and checks to see if it matches an intercepted ciphertext. With a probabilistic scheme, every plaintext message has a multitude of possible encodings, and the system chooses randomly among them. Even if you correctly guess the plaintext, there’s almost no chance of matching the random encryption. On decryption, however, all of the alternatives collapse to the same plaintext.

Cryptographic technology of this kind has become a routine part of life on the Internet—so routine that it often goes unnoticed. When you check your bank balance on the Web, or make an online purchase, you rely on a secure version of the hypertext transfer protocol (https rather than plain http), which provides a layer of encryption behind the scenes. Even Google searches are encrypted. These measures are meant to protect your messages while they are in transit. Encrypted communication shuts out Eve, who is sitting at the next table in Starbucks, tapping into your wifi connection. On the other hand, the cryptographic protocols conceal nothing from the recipients of your messages, who have the keys to decipher them. Usually, that’s just fine, because the intended recipient is a trusted party. Homomorphic encryption is the tool for those occasions when you don’t trust anyone, not even Bob.

**IN THIS SECTION**

EMAIL TO A FRIEND :

**Of Possible Interest**

**Essay**: Invitation to an Insect Rendezvous

**Feature Article**: Twisted Math and Beautiful Geometry

**Spotlight**: First Person: Exploring the Unconscious Brain

**Other Related Links**