Showing without Telling

Persuasion is both an art and a science – particularly if you want to disclose the least possible information to the person you're trying to convince.

How, for instance can one persuade a person who is color-blind that the two cards in his hand are of a different color? One way would be to rely on a device that measures wavelength (color), but that would be expensive and inconvenient. Prof. Oded Goldreich of the Computer Science and Applied Mathematics Department suggests a more efficient method – a dialogue that includes random questions.

The first step would be to write the names of the colors (say, red and green) on the back of the cards. Then the color-blind person would show us the front of one of the cards, selected at random, and ask us what the color was. If this process is repeated enough times and we consistently identified the color as the one written on the card's back, then the person would be persuaded that the cards' colors are different. It is a simple method, which relies on randomized interaction between the two parties. In addition, essentially, it doesn't disclose any information other than the claim itself (that the cards' colors are different). Thus it is called a “zero-knowledge proof.”

Goldreich's studies have shown that randomness, a factor usually viewed as an impediment to precise computation, can assist proof systems, especially zero-knowledge systems. Such proofs play an important role in the protection of privacy and confidential information in computational systems. 

Prof. Goldreich is the incumbent of the Meyer W. Weisgal Professorial Chair.