|
|
|
|
Probabilistic Proof Systems: A Primer
Foundations and Trends® in
Theoretical Computer Science
Volume 3 Issue 1
DOI: 10.1561/0400000023
Probabilistic Proof Systems: A Primer
Oded Goldreich
Department of Computer Science and Applied Mathematics, Weizmann Institute of Science, Rehovot, Israel, oded.goldreich@weizmann.ac.il
SUGGESTED CITATION:
Oded
Goldreich
(2008)
"Probabilistic Proof Systems: A Primer",
Foundations and Trends® in Theoretical Computer Science: Vol. 3: No 1, pp 1-91.
http:/dx.doi.org/10.1561/0400000023
Abstract
Various types of probabilistic proof systems have played a central rolein the development of computer science in the last
couple of decades. These proof systems deviate from the traditional concept of a proof by introducing randomization and interaction
into the verification process. Probabilistic proof systems carry an error probability (which is explicitly bounded and can
be decreased by repetitions), but they offer various advantages over deterministic proof systems.
This primer concentrates on three types of probabilistic proof systems: interactive proofs, zero-knowledge proofs, and Probabilistically
Checkable Proofs (PCP). Surveying the basic results regarding these proof systems, we stress the essential role of randomness
in each of them.
|
|
|
|
|
|
|
|
|