Proofs Probable

Throughout history, people have used ciphers and cryptography to hide information from prying eyes. Yet it was not until 1983, when graduate students Shafi Goldwasser and Silvio Micali, the recipients of the 2012 ACM A.M. Turing Award, published their paper "Probabilistic Encryption," that cryptographers actually defined what they were doing.

"They were the first to ask the question, ‘What exactly is all this trying to accomplish? What is the goal more precisely than, ‘I want to hide my data’?’" says Mihir Bellare, professor of computer science and engineering at the University of California, San Diego, and a former Ph.D. student under Micali at the Massachusetts Institute of Technology (MIT); he is also a co-author of several research papers with both. "It’s in some ways amazing to think that in 2,000 years, people have looked at this and they had never seriously asked themselves what it means to break a cryptographic system."

In developing a formal definition of security, the two came up with the idea that an encryption method would be secure if an adversary given two encrypted messages could not have the slightest probabilistic advantage in distinguishing them from each other, even knowing what the two messages contained. They labeled this concept "semantic security," saying it incorporates the idea that even partial information about messages, even relationships between messages, should be hidden by their encryption.

"We designed randomized encryption methods for which you can prove that the time it would take an adversary to learn any information about encrypted messages is no less than the time it would take him to solve a mathematical problem believed to be intractable, such as factoring large numbers," says Goldwasser, a professor in the Computer Science and Artificial Intelligence Laboratory (CSAIL) at MIT and at the Weizmann Institute of Science in Israel.

"A lot of the work prior to theirs just was not very rigorous," says Ronald Rivest, a fellow professor at CSAIL and a 2002 Turing Award co-recipient for his work developing the RSA method of public key cryptography. "It was heuristic in character. It didn’t have a very precise definition of what security meant." Security is tricky, he says, because it is often a negative property; it’s not about showing that you can do something, but about showing that someone else cannot do it.

Together with Charles Rackoff of the University of Toronto, Goldwasser and Micali came up with interactive proofs, a way to demonstrate that a person has proven a theorem to another person without the other person learning how to prove the theorem. "Using interactive proofs, you can actually get convinced with overwhelming probability of something that would have taken too long to prove with classical proofs," says Micali, also a CSAIL professor.

An interactive proof may be thought of as a game between a prover and a verifier that involves a small number of moves. If the theorem is correct, the prover wins every game; if it’s false, the prover wins less than half the time. "Clever interactive proofs can convince me that things are correct without involving me in too-time-consuming work," Micali says.

"A lot of the work prior to theirs just was not very rigorous." —RON RIVEST

Interactive proofs have led to wider study of new ways to write and check proofs. One such method, probabilistically checkable proofs, requires checking only some fraction of the proof chosen at random; if the checked portion is correct, that strongly suggests the whole proof is correct. If it is incorrect, there is a good probability that other spots checked would be wrong, too.

Goldwasser, Micali, and Rackoff also developed the concept of zero-knowledge proofs, which allow the user to convince someone else of the correctness properties of a piece of information, without actually revealing what that information is. A person using zero-knowledge proofs could demonstrate that she was authorized to access a secure system, without revealing her secret identifying information; zero-knowledge proofs could be used to verify that a tally of encrypted votes was computed correctly, without showing how each individual voted. "You can convince me a statement is correct without telling me why," Micali says. That ability would make it easier for multiple parties, such as businesses with sensitive financial information, to work together without revealing their secrets. "It’s a way to enhance the ability of people to interact," he says.

"I can’t tell you how surprised I was when I first heard the concept of zero-knowledge," says Rivest.

That was not their only unexpected contribution to the field, he says. "The necessity of using randomness in encryption was surprising to many people."

Still, it’s important. To start with, the person encrypting the data picks his approach at random, thus denying the adversary the ability to know when the same message is being encrypted and sent again. In interactive proofs, the two parties trade questions and answers, with the verifier trying to catch the prover in a lie. Because the verifier tosses a coin to choose his questions at random, the prover cannot anticipate them, or be ready with answers simply by repeating those from a previous round of questioning.

Another key notion is that these proofs allow for the possibility of error, as long as it is a very small possibility. "If I am a liar, there is a small chance you will not catch me, but with overwhelming probability you will find an error," Goldwasser says. Relying on overwhelming probability rather than 100% certainty provides cryptographers with enough freedom to make these proofs useful, she explains. "In all of these proofs there is imperfection, and that’s what allows this flexibility."

As it turns out, extensions of their theory of proofs provide a new way to classify difficult problems, which is important for the study of computational complexity.

When Micali and Goldwasser began their work in the early 1980s, today’s Internet was a distant dream, and there were no cloud computing or mobile applications to make the need for data security as obvious as it is now. While their focus was largely on theory, it has become the basis for advanced cryptographic schemes that are starting to be introduced in practice, Rivest says.

"The necessity of using randomness in encryption was surprising to many people."

Bellare says the two laid the foundation for modern cryptography. "The field was created by their ideas 30 years ago," he says. It was not just their theoretical work, but their way of expressing their ideas, using such concepts as games and adversaries, that fired other researchers’ imaginations. "They had a very strong sort of social and cultural impact, because they had a way of expressing ideas that was very catching," Bellare says.

The two do not yet know what they will do with the $250,000 prize that goes with the award, though Goldwasser says their children already have decided it should fund family trips to soccer matches in far-off countries.

Micali’s advice for young computer scientists is to cultivate an initial sense of irreverence, a certain lack of respect for what has gone before. "You don’t want to be constrained by current theories when you develop your own," he says. "Just go for what you like and be as irreverent as you can and then try to restore law and order afterwards."

Goldwasser says scientists should trust their own tastes, and take the time to really chew on a problem that interests them. "It’s very useful to kind of try to think of the problem from lots of different directions," she says. Her other admonition: "Don’t stop too early." Sometimes, she says, researchers will solve a problem, write it up for a conference, and move on without considering other aspects of their solution. "If you come up with something new, and it’s yours, stick with it," she says.

Back to Top