Chapter 03: Definitions and Technical Preliminaries

Interactive Proofs

Given: function $f$ mapping $\{0,1{\}}^n$ to finite range $\mathcal{R}$, a k-message IP for $f$

• probabilistic verifier $\mathcal{V}$ time $poly(n)$.

what does it mean to be probabilistic?

• deterministic prover $\mathcal{P}$
• P and V exchange messages $m_i\forall i\in [0,k]$ alternatively. Both work as next-message-computing algorithms, i.e. if it’s V’s turn, it’s algorithm is run on $x,m_1,\dots ,m_{i-1}$.

Properties:

1. Completeness: For every $x\in \{0,1{\}}^n$: $Pr[\text{out}(\mathcal{V},x,r,\mathcal{P})=1]\ge 1-{\delta }_c$
2. Soundness: For every $x\in \{0,1{\}}^n$ and every deterministic prover strategy $P^{\prime }$, if ${\mathcal{P}}^{\prime }$ sends a value $y\ne f(x)$, then $Pr[\text{out}(\mathcal{V},x,r,{\mathcal{P}}^{\prime })=1]\le {\delta }_s$

An IP is valid if ${\delta }_c,{\delta }_s\le \frac{1}{3}$

what is the difference between message and rounds?

Argument system

• Statistical soundness: computationally unbounded provers ${\mathcal{P}}^{\prime }$
• computational soundness: prover runs in poly time

Argument system for function $f$ is an IP for $f$ 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 ${\delta }_c=0$ which is what most proof systems utilise.
• Soundness error: ${\delta }_s\le \frac{1}{\mid \mathbb{F}\mid }$ is what most proof systems target or able to achieve. ${\delta }_s\le \frac{1}{3}$ 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 ${\mathcal{P}}^{\prime }$, then there is a deterministic prover strategy achieving the same.

IP for language vs functions

We’ve so far defined IP for function $f$, complexity theorists often work in the concept of language. A decision problem can be associated with subset $\mathcal{L}\in \{0,1{\}}^n$ where this subset is termed as language.

IP for language, given a public input $x\in \{0,1{\}}^n$, let $f_{\mathcal{L}}:x\to \left\{0,1\right\}$ be the corresponding decision problem. So, $\mathcal{V}$ outputs $f_{\mathcal{L}}(x)=0$, if x not in $\mathcal{L}$, and 1 if $f_{\mathcal{L}}(x)=1$. Difference between IP for language and function is that for language, there doesn’t need to be a valid proof if $f_{\mathcal{L}}(x)=0$, 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

schwartz-zippel-lemma

Multilinear extensions

sumcheck-and-gkr

Also introduces algorithm for evaluation multilinear extensions in $v$ variables in $\mathcal{O}(2^v)$.