7 min read
On this page

Interactive Proofs

The Interactive Proof Model

An interactive proof system for a language L consists of two parties:

  • Prover (P): Computationally unbounded, trying to convince the verifier that x is in L
  • Verifier (V): Probabilistic polynomial-time, trying to determine membership

The interaction consists of message exchanges. The system must satisfy:

  1. Completeness: If x is in L, the honest prover convinces V with probability >= 2/3
  2. Soundness: If x is not in L, no prover strategy convinces V with probability > 1/3

IP = class of languages having interactive proof systems. IP[k] restricts to k rounds of interaction.

Arthur-Merlin Games

Arthur-Merlin (AM) games (Babai, 1985) restrict the verifier's messages to be its random coin tosses (public coins). Merlin (the prover) sees Arthur's randomness.

  • MA: Merlin sends a message, then Arthur checks (one round, Merlin first)
  • AM: Arthur sends random string, Merlin responds, Arthur checks (one round, Arthur first)
  • AM[k]: k rounds of alternation

Theorem (Goldwasser-Sipser, 1986): IP[k] = AM[k] for k >= 2. Private coins do not help when there are at least two rounds. (For one round, MA may be weaker than IP[1], but this is open.)

Theorem (Babai-Moran, 1988): AM[k] = AM[2] = AM for any constant k. Constant-round interactive proofs collapse to two rounds.

Consequence: The entire constant-round interactive proof hierarchy collapses to AM. For superlogarithmic rounds, the situation changes dramatically (IP = PSPACE uses polynomially many rounds).

Graph Non-Isomorphism in AM

The first striking example of interactive proofs: Graph Non-Isomorphism (GNI) has an interactive proof, despite not being known to be in NP.

Protocol: Given graphs G_0, G_1:

  1. Verifier randomly picks b in {0,1}, randomly permutes G_b to get H, sends H to Prover
  2. Prover determines which G_b the graph H came from, sends b' to Verifier
  3. Verifier accepts if b' = b

If G_0 is not isomorphic to G_1, the prover can always distinguish (completeness). If G_0 is isomorphic to G_1, then H is equally likely to have come from either, so no prover can do better than random guessing (soundness 1/2, amplifiable).

This places GNI in coAM = AM (by the collapse theorem), suggesting that Graph Isomorphism is not NP-complete (unless PH collapses).

The Sum-Check Protocol

The sum-check protocol (Lund-Fortnow-Karloff-Nisan, 1992) is the foundational technique for interactive proofs. It verifies claims of the form:

H = sum over (x_1,...,x_n) in {0,1}^n of g(x_1,...,x_n)

where g is a low-degree polynomial over a finite field F.

Protocol:

  1. Prover claims the sum equals H
  2. Round 1: Prover sends univariate polynomial s_1(x_1) = sum over x_2,...,x_n of g(x_1,x_2,...,x_n). Verifier checks s_1(0) + s_1(1) = H, then picks random r_1 in F
  3. Round i: Prover sends s_i(x_i) = sum over x_{i+1},...,x_n of g(r_1,...,r_{i-1},x_i,...,x_n). Verifier checks s_i(0) + s_i(1) = s_{i-1}(r_{i-1}), then picks random r_i
  4. Final round: Verifier checks s_n(r_n) = g(r_1,...,r_n) directly

Soundness: If the prover lies at any round, the probability that the verifier fails to catch this is at most d/|F| per round (Schwartz-Zippel), where d is the degree of g. Over n rounds, the total error is at most nd/|F|, which is negligible for large fields.

Complexity: n rounds, each with a polynomial of degree at most d, so communication is O(n * d * log|F|).

IP = PSPACE (Shamir's Theorem)

Theorem (Shamir, 1992): IP = PSPACE.

PSPACE is in IP: Reduce any PSPACE problem to TQBF. Arithmetize the quantified Boolean formula: replace AND with multiplication, OR with 1-(1-a)(1-b), quantifiers with sums and products over {0,1}. Apply the sum-check protocol.

The key difficulty: after arithmetization, the degree of the polynomial may blow up with each quantifier. Shamir's trick: after each summation step, linearize the polynomial by introducing a new round where the verifier checks that a degree-reducing substitution is correct. This keeps the degree bounded throughout.

IP is in PSPACE: The verifier is polynomial-time, and PSPACE can enumerate over all possible random strings, simulating the optimal prover strategy. For each verifier message, the PSPACE machine computes the prover response that maximizes acceptance probability (this is a game tree evaluation solvable in PSPACE).

Consequences:

  • coNP is in IP (since PSPACE contains coNP)
  • #P is in IP (since PSPACE contains #P; the sum-check protocol directly handles counting)
  • The polynomial hierarchy is in IP

The GKR Protocol

The GKR protocol (Goldwasser-Kalai-Rothblum, 2008/2015) provides an efficient interactive proof for delegated computation: a weak verifier checks that a powerful server correctly evaluated a circuit.

Setup: Given a layered arithmetic circuit C of depth d, size S:

  1. Verifier wants to check C(x) = y
  2. Reduce the claim about the output layer to a claim about the previous layer using sum-check
  3. Iterate through all d layers
  4. At the input layer, the verifier checks directly

Complexity:

  • Prover: O(S log S) time (quasilinear in circuit size)
  • Verifier: O(n + d log S) time (sublinear in circuit size for small depth)
  • Communication: O(d log S)

GKR is foundational for verifiable computation and forms the basis of modern interactive proof systems used in cryptographic protocols and zero-knowledge proofs (SNARKs, STARKs).

Zero-Knowledge Proofs

A zero-knowledge proof system reveals nothing beyond the validity of the statement. Formally, for language L with interactive proof (P, V):

Zero-Knowledge Property: For every PPT verifier V*, there exists a PPT simulator S such that the output distribution of S(x) is indistinguishable from the view of V* in the interaction with P on input x in L.

Three variants by indistinguishability notion:

  • Perfect ZK: Distributions are identical
  • Statistical ZK: Distributions have negligible statistical distance
  • Computational ZK: Distributions are computationally indistinguishable

ZK Proof for Graph Isomorphism

Given isomorphic graphs G_0, G_1 (prover knows the isomorphism pi):

  1. Prover picks random permutation sigma, sends H = sigma(G_0) to verifier
  2. Verifier picks random b in {0,1}, sends to prover
  3. Prover responds with isomorphism from G_b to H

Completeness: Honest prover knows pi and sigma, can always respond. Soundness: If G_0 is not isomorphic to G_1, prover cannot respond to both b=0 and b=1. Zero-Knowledge: Simulator picks random b', random sigma', computes H' = sigma'(G_b'), outputs the transcript. This is identically distributed to the real interaction.

ZK Proof for Graph 3-Coloring (and NP)

Theorem (Goldreich-Micali-Wigderson, 1986): Every language in NP has a computational zero-knowledge proof (assuming one-way functions exist).

Protocol for 3-Coloring:

  1. Prover randomly permutes the color names, commits to each vertex's color using a commitment scheme
  2. Verifier picks a random edge (u, v)
  3. Prover opens commitments for u and v
  4. Verifier checks that the revealed colors are different

Soundness: If the graph is not 3-colorable, at least one edge is monochromatic under any coloring, caught with probability >= 1/|E|. Zero-Knowledge: Simulator tries random edge, generates fake commitments; rewinds if the verifier picks a different edge. Expected poly-time simulation.

Completeness of Zero-Knowledge

  • SZK (statistical ZK): Contains graph non-isomorphism, lattice problems. SZK is closed under complement.
  • CZK (computational ZK): Contains all of NP (assuming OWFs). Under cryptographic assumptions, CZK = IP = PSPACE.

MIP: Multi-Prover Interactive Proofs

MIP uses multiple provers who cannot communicate with each other during the protocol. The verifier can cross-check provers' answers.

Theorem (Babai-Fortnow-Lund, 1991): MIP = NEXP.

With quantum entanglement between provers, the class becomes MIP = RE* (the class of recursively enumerable languages), proved by Ji-Natarajan-Vidick-Wright-Yuen (2020), resolving Connes' embedding conjecture.

Structural Results

| Class | Characterization | |---|---| | IP | PSPACE | | AM | Contains Graph Non-Isomorphism; AM is in Pi_2^P | | coAM | AM (AM = coAM) | | MIP | NEXP | | MIP* | RE | | SZK | Closed under complement; contains lattice problems | | PZK | Known to contain few natural problems |

Applications

  • Verifiable computation: Delegate computation to untrusted servers (GKR, Muggles)
  • Cryptographic protocols: ZK proofs are building blocks for secure computation, authentication, and blockchain systems (SNARKs, STARKs)
  • Complexity separations: IP = PSPACE is a non-relativizing result, breaking the Baker-Gill-Solovay barrier
  • Hardness amplification: Interactive proofs enable transforming weak hardness to strong hardness via parallel repetition

Historical Significance

The IP = PSPACE theorem was one of the most surprising results in complexity theory. It showed that interaction and randomness together are extraordinarily powerful -- far more than either alone. The proof technique (arithmetization + sum-check) is a paradigm example of an algebraic method overcoming barriers that combinatorial approaches could not.