Böcker av Oded Goldreich

An interactive proof system is called doubly-efficient if the prescribed prover strategy can be implemented in polynomial-time and the verifier's strategy can be implemented in almost-linear time. This book surveys some of the known results regarding doubly-efficient interactive proof systems.

This primer concentrates on three types of probabilistic proof systems: interactive proofs, zero-knowledge proofs, and probabilistically checkable proofs. Surveying the basic results regarding these proof systems, the primer stresses the essential role of randomness in each of them.