Oded Goldreich - Poster (2003)

From Weizmann's annual report 2003
click for big (5MB!!!)

(The text is reproduced on the right column)

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.

The above text is based on the Graph Non-Isomoprphism (zero-knowledge) proof that was presented by Goldreich, Micali and Wigderson in Proofs that Yield Nothing But their Validity or All Languages in NP have Zero-Knowledge Proofs, Journal of the ACM, July 1991.

Zero-knowledge proofs are probabilistic and interactive proofs that efficiently demonstrate membership in the language without conveying any additional knowledge. The wide applicability of zero-knowledge was demonstrated in the aforementioned work. In particular, assuming the existence of one-way functions, it is shown that every language in NP has a zero-knowledge proof system. For further detail on this (and other related) work see Goldreich's webpage on zero-knowledge.

Back to Oded Goldreich's homepage.