NP can be viewed as a one-round interactive proof where the prover sends a witness and the verifier checks it deterministically. How do multiple rounds and verifier randomness add power?
Think about your answer, then reveal below.
Model answer: Multiple rounds let the verifier probe the prover adaptively — each challenge depends on previous responses, forcing the prover to maintain consistency across a complex structure. Verifier randomness prevents the prover from predicting challenges, so a cheating prover cannot prepare consistent responses in advance. Together, these features let IP capture PSPACE (far beyond NP): the verifier can check computations that no static witness can encode, such as verifying quantified Boolean formulas (QBF) or counting problems.
The power comes from adaptivity and unpredictability. A static witness (NP) proves existence claims. Interactive proofs can verify counting claims (#SAT), uniqueness claims, and universal claims (for-all statements) by using random sampling and algebraic techniques across multiple rounds. The IP = PSPACE result shows this power is maximal for polynomial-time verifiers.
Question 2 Multiple Choice
The Fiat-Shamir heuristic replaces the verifier's random challenges with H(transcript-so-far) where H is a hash function. This transforms an interactive protocol into a non-interactive one. What security model does this require?
AThe standard model — Fiat-Shamir is provably secure under any hash function
BThe random oracle model — H is modeled as a truly random function. In the standard model (with any concrete hash function), Fiat-Shamir can be insecure for some protocols, though it works well in practice for many specific constructions
CThe quantum random oracle model — security requires quantum-resistant hash functions
DNo security model — Fiat-Shamir is a heuristic with no formal guarantees
In the random oracle model, the hash function is an idealized random function that the adversary can only query as a black box. This prevents the adversary from exploiting any structure in the hash to predict or control challenges. Pointcheval and Stern proved Fiat-Shamir signatures secure in the ROM. However, Goldwasser and Kalai showed there exist interactive proofs where Fiat-Shamir is insecure for ANY hash function — so the ROM idealization is essential, not just convenient. Despite this, Fiat-Shamir works well for specific, carefully designed protocols and is used extensively (Schnorr signatures, zk-SNARKs).
Question 3 True / False
IP = PSPACE means a polynomial-time verifier with access to an all-powerful prover can verify exactly the same set of problems that can be solved with polynomial space.
TTrue
FFalse
Answer: True
Shamir's 1990 proof showed IP = PSPACE by giving an interactive proof for QBF (the PSPACE-complete problem of evaluating fully quantified Boolean formulas). The protocol uses arithmetization (converting Boolean formulas into polynomials over finite fields) and the sum-check protocol (an interactive protocol for verifying the sum of a multivariate polynomial over a Boolean hypercube). Since QBF is PSPACE-complete, this gives interactive proofs for all of PSPACE. Combined with the easy direction (PSPACE can simulate any interactive proof), this gives the equality.
Question 4 Multiple Choice
Graph non-isomorphism (proving two graphs are NOT isomorphic) has an interactive proof but is not known to be in NP. Why is it easier for interactive proofs?
AInteractive proofs can handle exponential-size witnesses that NP cannot
BNP verification requires a short certificate proving non-isomorphism, which seems to require checking all n! possible mappings. In the interactive proof, the verifier secretly picks one of the two graphs, randomly permutes it, and asks the prover to identify which one. If the graphs are non-isomorphic, a powerful prover can always distinguish them; if they are isomorphic, no prover can tell which was chosen (probability 1/2). Repeated rounds drive the error down
CInteractive proofs can use quantum entanglement to verify non-isomorphism
DThe prover compresses the exponential witness into a polynomial-size response
This is one of the earliest and most elegant interactive proofs. It beautifully illustrates how verifier randomness adds power: the verifier creates a challenge that an honest prover can always answer correctly (by their computational power) but a dishonest prover (claiming non-isomorphic graphs are isomorphic) cannot answer better than random guessing. The protocol also happens to be zero-knowledge, which showed early on that ZK proofs extend beyond NP.
Question 5 Short Answer
Arthur-Merlin (AM) protocols restrict the verifier to sending only its random coins (public-coin). Goldwasser and Sipser showed that AM has the same power as general IP (private-coin). Why is this surprising?
Think about your answer, then reveal below.
Model answer: Intuitively, a verifier who hides its randomness (private-coin) seems more powerful — it can design challenges that depend on the prover's responses in ways the prover cannot anticipate. Goldwasser-Sipser showed this intuition is wrong: any private-coin protocol can be converted to a public-coin one with the same power (up to a constant number of additional rounds). This means the verifier gains no advantage from secrecy, which is surprising because the prover in a public-coin protocol knows exactly what random values the verifier used.
The result uses the technique of having the prover help select a nearly-uniform hash function that maps the random string to a useful challenge. Since the prover is computationally unbounded, it can perform this additional computation. The practical implication is that public-coin protocols (which are simpler to analyze and to convert to non-interactive form via Fiat-Shamir) lose nothing compared to private-coin ones.