1 Preliminaries

Definition 1.1 Interactive Oracle Proofs of Proximity (IOPP)

A \(k\)‑round public‑coin interactive‑oracle proof of proximity (IOPP) for a ternary relation \(\mathcal R = \{ (x,y,w)\} \) is an interactive protocol between a prover \(\mathsf P\) and a verifier \(\mathsf V\) defined as follows.

The prover receives \((x,y,w)\), while the verifier receives \(x\) and oracle access to \(y\).
For each round \(i\in [k]\) the verifier sends a uniformly random message \(\alpha _i\) to the prover, who responds with a proof string \(\pi _i\).
After \(k\) rounds, the verifier may query \(y\) and the proof strings \(\pi _1,\dots ,\pi _k\) and finally outputs a decision bit.

Formally, let \(\mathsf{IOP}=(\mathsf P,\mathsf V)\) where \(\mathsf P\) is an interactive algorithm and \(\mathsf V\) is an interactive‑oracle algorithm. The protocol has perfect completeness and soundness error \(\beta \) if the following conditions hold.

Perfect completeness.

For every \((x,y,w)\in \mathcal R\),

\[ \Pr _{\alpha _1,\ldots ,\alpha _k}\! \Bigl[ \mathsf V^{y,\pi _1,\ldots ,\pi _k}(x,\alpha _1,\ldots ,\alpha _k)=1 \; \Big|\; \pi _1\leftarrow \mathsf P(x,y,w),\; \dots ,\; \pi _k\leftarrow \mathsf P(x,y,w,\alpha _1,\ldots ,\alpha _k) \Bigr]=1. \]

Soundness.

For every \((x,y)\notin L(\mathcal R)\) and every (unbounded) malicious prover \(\widetilde{\mathsf P}\),

\[ \Pr _{\alpha _1,\ldots ,\alpha _k}\! \Bigl[ \mathsf V^{y,\pi _1,\ldots ,\pi _k}(x,\alpha _1,\ldots ,\alpha _k)=1 \; \Big|\; \pi _1\leftarrow \widetilde{\mathsf P}(\alpha _1),\; \dots ,\; \pi _k\leftarrow \widetilde{\mathsf P} (x,y,\alpha _1,\ldots ,\alpha _k) \Bigr]\le \beta (x,y). \]

When the soundness error depends only on the input lengths and on the proximity \(\delta \) of \(y\) to the language

\[ L_x \; :=\; \{ \, y' \mid \exists w,\, (x,y',w)\in \mathcal R\} , \]

we write \(\beta \bigl(|x|,|y|,\delta \bigr)\), or simply \(\beta (\delta )\) when \(|x|\) and \(|y|\) are clear from context.

Definition

Definition 1.2

Let \(k\in \mathbb {N}\) be an integer, \(\mathbb {F}\) be a finite field and \(\mathcal{L}\subset \mathbb {F}\) be a subset of \(\mathbb {F}\). Then

\[ \mathcal{L}^k := \{ x^k \text{ s.t. } x \in \mathcal{L}\} \]

Definition 1.3 Reed-Solomon Code

✓

The Reed-Solomon code over finite field \(\mathbb {F}\), evaluation domain \(\mathcal{L}\subseteq \mathbb {F}\) and degree \(d\in \mathbb {N}\) is the set of evaluations (over \(\mathcal{L}\)) of univariate polynomials (over \(\mathbb {F}\)) of degree less than \(d\):

\[ \mathrm{RS}[\mathbb {F},\mathcal{L},d]:=\; \bigl\{ \, f : \mathcal{L}\to \mathbb {F}\; \big|\; \exists \, \hat{f} \, \in \mathbb {F}^{{\lt}d}[X]\text{ such that } \forall x \in \mathcal{L},\; f(x) = \hat{f}(x)\bigr\} . \]

The rate of \(\mathrm{RS}[\mathbb {F},\mathcal{L},d]\) is \(\rho := \frac{d}{\lvert \mathcal{L}\rvert }\).

Given a code \(\mathcal{C}:= \mathrm{RS}[\mathbb {F},\mathcal{L},d]\) and a function \(f : \mathcal{L}\to \mathbb {F}\), we sometimes use \(\hat{f} \in \mathbb {F}^{{\lt}d}[X]\) to denote a nearest polynomial to \(f\) on \(\mathcal{L}\) (breaking ties arbitrarily).

Remark 1.4

Note that the evaluation domain \(\mathcal{L}\subseteq \mathbb {F}\) is a non-empty set.

Definition 1.5

For a Reed-Solomon code \(\mathcal{C}:= \mathrm{RS}[\mathbb {F},\mathcal{L},d]\), parameter \(\delta \in [0,1]\), and a function \(f:\mathcal{L}\to \mathbb {F}\), let \(\mathsf{List}(f,d,\delta )\) denote the list of codewords in \(\mathcal{C}\) whose relative Hamming distance from \(f\) is at most \(\delta \). We say that \(\mathcal{C}\) is \((\delta ,l)\)-list decodable if

\[ \bigl|\mathsf{List}(f,d,\delta )\bigr| \leq l \quad \text{for every function } f. \]

The Johnson bound provides an upper bound on the list size of this Reed-Solomon code:

Theorem 1.6 Johnson bound

The Reed-Solomon code \(\mathrm{RS}[\mathbb {F},\mathcal{L},d]\) is \((1-\sqrt{\rho }-\eta ,\frac{1}{2\eta \rho })\)-list-decodable for every \(\eta \in (0,1-\sqrt{\rho })\), where \(\rho :=\frac{d}{|\mathcal{L}|}\) is the rate of the code.