 Probabilistic Proof Systems: A Primer by Oded Goldreich

Author-hosted primer dated30June2008. Sections1.1.2–1.2, printedpp.6–8, give prover/verifier and quantified completeness/soundness definitions; Construction1.3, pp.9–10, gives the random-relabeling graph-non-isomorphism protocol. Construction2.3 and its following simulation discussion, printedpp.26–28, treat graph-isomorphism zero knowledge; section2.3, pp.32–34, treats proofs of knowledge.