Srikar: Created page with "The story of the PCP Theorem begins at MIT in the early 1980s, with a paper that would win the first ever G ̈odel Prize: The Knowledge Complexity of Interactive Proof Systems..."

2020-07-01T16:59:43Z

Created page with "The story of the PCP Theorem begins at MIT in the early 1980s, with a paper that would win the first ever G ̈odel Prize: The Knowledge Complexity of Interactive Proof Systems..."

New page

The story of the PCP Theorem begins at MIT in the early 1980s, with a paper that would win the first ever G ̈odel Prize: The Knowledge Complexity of Interactive Proof Systems, by Goldwasser, Micali, and Rackoff. This paper was first published in STOC ’85. However drafts of it are said to have existed as early
Shafi Goldwasser Silvio Micali Charlie Rackoff
as late ’82; indeed, it was supposedly cited in at least one paper from ’83. The story also goes that this paper was rejected from FOCS ’83, STOC ’84, and FOCS ’84, although it’s not clear what form the paper was in for these rejections.
Goldwasser, Micali, and Rackoff were actually interested in the philosophical notion of what it means to prove something, although the main motivation of their paper was cryptographic. This paper introduced two new notions: interactive proofs, and zero-knowledge proofs.

This is the most general notion of efficient proof that GMR could think of; they modeled it on the idea of students in a classroom interacting with a lecturer giving a proof. As for their other notion of zero-knowledge proofs, we won’t get into any details here, except to say that whereas in a tradition proof you may “learn” many things about the theorem in addition to the fact that it’s true, in an interactive proof it can be pos- sible that you learn “zero additional information” beyond the fact that the theorem is true. GMR’s main example was the “quadratic non-residuosity” problem. It is not hard to prove in NP that a number is a quadratic non-residue, by giving the factorization of the modulus as a witness; however this reveals a lot of information. GMR gave a “zero-knowledge” proof of this fact. This is certainly an interesting example of a zero-knowledge proof, but not such an interesting example of an interactive proof, since the problem is already in NP.

The Knowledge Complexity of Interactive Proof Systems - Revision history

Srikar: Created page with "The story of the PCP Theorem begins at MIT in the early 1980s, with a paper that would win the first ever G ̈odel Prize: The Knowledge Complexity of Interactive Proof Systems..."