Probabilistic Proof Systems
Various types of probabilistic proof systems have played a central role in the development of computer science in the last decade. In this chapter, we concentrate on three such proof systems — interactive proofs, zero-knowledge proofs, and probabilistic c
- PDF / 4,033,122 Bytes
- 34 Pages / 439.37 x 666.142 pts Page_size
- 22 Downloads / 212 Views
A proof is whatever convinces me. Shimon Even, answering a student's question in his Graph Algorithms class (1978)
Summary - Various types of probabilistic proof systems have played a central role in the development of computer science in the last decade. In this chapter, we concentrate on three such proof systems - interactive proofs, zero-knowledge proofs, and probabilistic checkable proofs - stressing the essential role of randomness in each of them.
2.1 Introduction The glory attached to the creativity involved in finding proofs, makes us forget that it is the less glorified procedure of verification which gives proofs their value. Philosophically speaking, proofs are secondary to the verification procedure; whereas technically speaking, proof systems are defined in terms of their verification procedures. The notion of a verification procedure assumes the notion of computation and furthermore the notion of efficient computation. This implicit assumption is made explicit in the definition of NP, in which efficient computation is associated with (deterministic) polynomial-time algorithms. Definition 2.1 (NP-proof systems): Let S ~ {0, 1}* and v : {0, 1}* x {0, 1}* >--> {0, 1} be a function so that x E S if and only if there exists a wE {0, 1}* such that v(x,w) = 1. If vis computable in time bounded by a polynomial in the length of its first argument then we say that S is an NP-set and that v defines an NP-proof system. Traditionally, NP is defined as the class of NP-sets. Yet, each such NP-set can be viewed as a proof system. For example, consider the set of satisfiable O. Goldreich, Modern Cryptography, Probabilistic Proofs and Pseudorandomness © Springer-Verlag Berlin Heidelberg 1999
40
2. Probabilistic Proof Systems
Boolean formulae. Clearly, a satisfying assignment 1r for a formula ¢ constitutes an NP-proof for the assertion "¢is satisfiable" (the verification procedure consists of substituting the variables of ¢ by the values assigned by 1r and computing the value of the resulting Boolean expression). The formulation of NP-proofs restricts the "effective" length of proofs to be polynomial in length of the corresponding assertions (since the runningtime of the verification procedure is restricted to be polynomial in the length of the assertion). However, longer proofs may be allowed by padding the assertion with sufficiently many blank symbols. So it seems that NP gives a satisfactory formulation of proof systems (with efficient verification procedures). This is indeed the case if one associates efficient procedures with deterministic polynomial-time algorithms. However, we can gain a lot if we are willing to take a somewhat non-traditional step and allow probabilistic verification procedures. In particular, - Randomized and interactive verification procedures, giving rise to interactive proof systems, seem much more powerful (i.e., "expressive") than their deterministic counterparts. - Such randomized procedures allow the introduction of zero-knowledge proofs which are of great theoretical and practica
Data Loading...