Interactive Proofs

Given: function mapping to finite range , a k-message IP for

  • probabilistic verifier time .

what does it mean to be probabilistic?

  • deterministic prover
  • P and V exchange messages alternatively. Both work as next-message-computing algorithms, i.e. if it’s V’s turn, it’s algorithm is run on .


  1. Completeness: For every :
  2. Soundness: For every and every deterministic prover strategy , if sends a value , then

An IP is valid if

what is the difference between message and rounds?

Argument system

  • Statistical soundness: computationally unbounded provers
  • computational soundness: prover runs in poly time

Argument system for function is an IP for where adversarial prover strategy only runs in poly time.

Why argument systems perform better than IP?

Because due to adversarial prover being computationally bounded, argument systems can use cryptographic primitives which can’t be broken by polynomial time adversaries. Thus, argument systems often have reusability, public verifiability, etc.

  • Perfect vs Imperfect Completeness: Perfect completeness refers to which is what most proof systems utilise.
  • Soundness error: is what most proof systems target or able to achieve. is merely a convention.
  • Public vs Private randomness: When verifiers randomness is internal, its called Private randomness, and when Verifiers randomness is made public, i.e. coin tosses can be seen by prover as soon as it is done, then the randomness is public.
    • Public randomness can utilise cryptographic primitives such as Fiat-Shamir transform to convert an interactive argument system non-interactive.
  • Deterministic vs probabilistic provers: In IPs, soundness is required to hold against deterministic adversarial prover. Note that: if there is a probabilistic cheating prover , then there is a deterministic prover strategy achieving the same.

IP for language vs functions

We’ve so far defined IP for function , complexity theorists often work in the concept of language. A decision problem can be associated with subset where this subset is termed as language.

IP for language, given a public input , let be the corresponding decision problem. So, outputs , if x not in , and 1 if . Difference between IP for language and function is that for language, there doesn’t need to be a valid proof if , but for function, there does need to be a valid proof strategy that convinces the verifier.

NP and IP

  • IP: class of all languages solvable by an interactive, randomised proof system with polynomial time verifier.
  • NP: class of language obtained by restricting IP to be non-interactive and deterministic

Schwartz Zippel Lemma


Multilinear extensions


Also introduces algorithm for evaluation multilinear extensions in variables in .