Interactive Proof Systems (2010)

This tutorial provides a survey of applications of interactive proof systems in cryptography and outlines recent development with challenge-response systems.

Outline of the Presentation

1. Applications of protocols: signature schemes, group signature schemes, verifiable protocols including cash, voting, secret sharing. Recent industry development: DAA, U-Prove.
2. Interactive proof systems. Proofs and arguments. Proofs of knowledge. Witness hiding and witness indistinguishable protocols. Zero knowledge and honest verifier zero knowledge.
3. Efficient interactive proof systems. Homomorphic commitment schemes. Protocols with ’algebraic’ responses and with only a negligible soundness.
4. Protocols for Boolean OR and AND.
5. Committment schemes with groups of a hidden order.
6. Testing polynomial relations. ’Verification polynomials’ with witness replaced by Prover’s response. Top coefficient of verification polynomial produced with responses of Chaum-Schnorr style. Alternative ’algebraic’ responses. Testing polynomial identity, Schwartz-Zippel lemma. Protocols with multiple challenges.

Overview of protocols for a codeword of Goppa code and small error weight, small set difference, graph isomorphism and Hamiltonicity, multiple substring matching, boolean OR, exact threshold, blind signature scheme.

Language of the course - Russian.

Tutor of the course:

V. Fedyukovych, GlobalLogic Ukraine