Interactive Proofs

Cryptography · Axiom Academy

Multi-round protocols where provers convince verifiers through challenge-response interactions 1. The Challenge-Response Paradigm An interactive proof system is a protocol between two parties: The protocol proceeds in rounds : the verifier sends random challenges, and the prover responds. After multiple rounds, the verifier decides whether to accept. 2. Sound and Complete Interactive Proofs An interactive proof system must satisfy two critical properties: 3. The Power of Randomness and Repetition The verifier's random challenges create an exponentially large space of possible interactions. A dishonest prover might succeed on one specific challenge, but cannot prepare for all possible challenges simultaneously. Error Reduction Through Repetition: If a single round has soundness error ε, repeating the protocol k times independently reduces the error exponentially: The class IP (Interactive Polynomial-time) consists of all languages that have interactive proof systems where the verifier runs in polynomial time. V runs in probabilistic polynomial time If x ∉ L: For all provers P*, Pr[V accepts] ≤ 1/3 5. Graph Non-Isomorphism Protocol A classic example: proving two graphs G₀ and G₁ are NOT isomorphic. This problem is believed to be outside NP, yet has an interactive proof! Verifier randomly picks b ∈ 0, 1 and creates a random isomorphic copy H of G_b Verifier sends H to the prover and asks: "Which graph is H isomorphic to?"

This is the written version of the interactive lesson above. See the full Cryptography course.