Dependencies

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

Given target degree \(d^*\in \mathbb {N}\), shifting parameter \(r\in \mathbb {F}\), functions \(f_1,\ldots ,f_m:\mathcal{L}\rightarrow \mathbb {F}\), and degrees \(0\leq d_1,\ldots ,d_m\leq {d}^*\), we define \(\mathsf{Combine}(d^*,r,(f_1,d_1),\ldots ,(f_m,d_m)):\mathcal{L}\rightarrow \mathbb {F}\) as follows:

Above, \(r_1:=1\), \(r_i:=r^{i-1+\sum _{j{\lt}i}(d^*-d_i)}\) for \(i{\gt}1\).

Given target degree \(d^*\in \mathbb {N}\), shifting parameter \(r\in \mathbb {F}\), function \(f:\mathcal{L}\rightarrow \mathbb {F}\), and degree \(0\leq d\leq d^*\), we define \(\mathsf{DegCor}(d^*,r,f,d)\) as follows.

(Observe that \(\mathsf{DegCor}(d^*,r,f,d)=\mathsf{Combine}(d^*,r,(f,d))\).)

Let \(f:\mathcal{L}\rightarrow \mathbb {F}\) be a function, \(k\in \mathbb {N}\) a folding parameter and \(\alpha \in \mathbb {F}\). For every \(x\in {\mathcal{L}}^k\), let \(\hat{p}_x\in \mathbb {F}^{{\lt}k}[X]\) be the polynomial where \(\hat{p}_x(y)=f(y)\) for every \(y\in {\mathcal{L}}\) such that \(y^k=x\). We define \(\mathsf{Fold}(f,k,\alpha ):\mathcal{L}\rightarrow \mathbb {F}\) as follows.

In order to compute \(\mathsf{Fold}(f,k,\alpha )(x)\) it suffices to interpolate the \(k\) values \(\{ f(y):y\in \mathcal{L}\text{ s.t. }y^k=x\} \) into the polynomial \(\hat{p}_x\) and evaluate this polynomial at \(\alpha \).

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.

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

Given a polynomial \(\hat{f}\in \mathbb {F}^{{\lt}d}[X]\), a folding parameter \(k\in \mathbb {N}\) and \(r\in \mathbb {F}\), we define a polynomial \(\mathsf{PolyFold}(\hat{f},k,r)\in \mathbb {F}^{d/k}[X]\) as follows. Let \(\hat{Q}[X,Y]\) be the bivariate polynomial derived from \(\hat{f}\) using Fact 2.6 with \(\hat{q}(X):=X^k\). Then \(\mathsf{PolyFold}(\hat{f},k,r)(X):=\hat{Q}(X,r)\).

Let \(\hat{f}\in \mathbb {F}^{{\lt}d}[X]\) be a polynomial and \(S\subseteq \mathbb {F}\) be a set, let \(\hat{V}_S\in \mathbb {F}^{{\lt}|S|+1}[X]\) be the unique non-zero polynomial with \(\hat{V}_S(x)=0\) for every \(x\in S\). The polynomial quotient \(\mathsf{PolyQuotient}(\hat{f},S)\in \mathbb {F}^{{\lt}d-|S|}[X]\) is defined as follows:

Let \(f:\mathcal{L}\to \mathbb {F}\) be a function, \(S\subseteq \mathbb {F}\) be a set, and \(\mathsf{Ans},\mathsf{Fill}: S\rightarrow \mathbb {F}\) be functions. Let \(\hat{\mathsf{Ans}}\in \mathbb {F}^{{\lt}|S|}[X]\) be the (unique) polynomial with \(\hat{\mathsf{Ans}}(x)=\mathsf{Ans}(x)\) for every \(x\in S\), and let \(\hat{V}_S\in \mathbb {F}^{{\lt}|S|+1}[X]\) be the unique non-zero polynomial with \(\hat{V}_S(x)=0\) for every \(x\in S\). The quotient function \(\mathsf{Quotient}\bigl(f,S,\mathsf{Ans},\mathsf{Fill}\bigr): \mathcal{L}\to \mathbb {F}\) is defined as follows:

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\):

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).

Let \(d^*\) be a target degree, \(f_1,\ldots ,f_m:\mathcal{L}\rightarrow \mathbb {F}\) be functions, \(0\leq d_1,\ldots ,d_m\leq d^*\) be degrees, \(\delta \in \min {\{ 1-{\mathsf{B}}^*(\rho ),1-\rho -1/|\mathcal{L}|\} }\) be a distance parameter, where \(\rho =d^*/|\mathcal{L}|\). If

then there exists \(S\subseteq \mathcal{L}\) with \(|S|\geq (1-\delta )\cdot |\mathcal{L}|\), and

Note that this implies \(\Delta (f_i,\mathrm{RS}[\mathbb {F},\mathcal{L},d_i]){\lt}\delta \) for every \(i\). Above, \({\mathsf{B}}^*\) and \({\mathsf{err}}^*\) are the proximity bound and error (respectively) described in Section 2.1.

For every function \(f:\mathcal{L}\rightarrow \mathbb {F}\), degree parameter \(d\in \mathbb {N}\), folding parameter \(k\in \mathbb {N}\), distance parameter \(\delta \in (0,\min \{ {\Delta (\mathsf{Fold}[f,k,r^{\mathsf{fold}}],\mathrm{RS}[\mathbb {F},{\mathcal{L}}^k, d/k]),1-{\mathsf{B}}^*(\rho )}\} )\), letting \(\rho :=\frac{d}{|\mathcal{L}|}\),

Above, \({\mathsf{B}}^*\) and \({\mathsf{err}}^*\) are the proximity bound and error (respectively) described in Section 2.1.

Let \(f:\mathcal{L}\rightarrow \mathbb {F}\) be a function, \(d\in \mathbb {N}\) be a degree parameter, \(s\in \mathbb {N}\) be a repetition parameter, and \(\delta \in [0,1]\) be a distance parameter. If \(\mathrm{RS}[\mathbb {F},\mathcal{L},d]\) be \((d,l)\)-list decodable then

Let \(f:\mathcal{L}\rightarrow \mathbb {F}\) be a function, \(d\in \mathbb {N}\) be the degree parameter, \(\delta \in (0,1)\) be a distance parameter, \(S\subseteq \mathbb {F}\) be a set with \(|S|{\lt}d\), and \(\mathsf{Ans},\mathsf{Fill}:S\rightarrow \mathbb {F}\) are functions. Suppose that for every \(u\in \mathsf{List}(f,d,\delta )\) there exists \(x\in S\) with \(\hat{u}(x)\neq \mathsf{Ans}(x)\). Then

where \(T:=\{ x\in \mathcal{L}\cap S: \hat{\mathsf{Ans}}(x)\neq f(x)\} \).

Consider \((\mathbb {F},M,d,k_0,\ldots ,k_M,\mathcal{L}_0,\ldots ,\mathcal{L}_M,t_0,\ldots ,t_M)\) and \(d_0,\ldots ,d_M\) as in Construction 3.2, and for every \(0\leq i\leq M\) let \(\rho _i:=d_i/|\mathcal{L}_i|\). For every \(f\notin \mathrm{RS}[\mathbb {F},\mathcal{L}_0,d_0]\) and every \(\delta _0,\ldots ,\delta _M\) where

• \(\delta _0\in (0,\Delta (f,\mathrm{RS}[\mathbb {F},\mathcal{L}_0,d_0])]\cap (0,1-{\mathsf{B}}^*(\rho _0))\)

• for every \(0{\lt}i\leq M\): \(\delta _i\in (0,\min {\{ 1-\rho _i-\frac{1}{|\mathcal{L}_i|},1-{\mathsf{B}^*(\rho _i)}\} })\), and

• for every \(0{\lt}i\leq M\): \(\mathrm{RS}[\mathbb {F},\mathcal{L}_i,d_i]\) is \((\delta _i,l_i)\)-list decodable,

STIR (Construction 3.2) has round-by-round soundness error \((\epsilon ^{\mathsf{fold}},\epsilon ^{\mathsf{out}}_1,\epsilon ^{\mathsf{shift}}_1,\ldots ,\epsilon ^{\mathsf{out}}_M,\epsilon ^{\mathsf{shift}}_M,\epsilon ^{\mathsf{fin}})\) where:

• \(\epsilon ^{\mathsf{fold}}\leq \mathsf{err}^*(d_0/k_0,\rho _0,\delta _0,k_0)\).

• \(\epsilon ^{\mathsf{out}}_i\leq \frac{l^2_i}{2}\cdot {\big(\frac{d_i}{|\mathbb {F}|-|\mathcal{L}_i|}\big)}^s\)

• \(\epsilon ^{\mathsf{shift}}_i\leq {(1-\delta _{i-1})}^{t_{i-1}}+\mathsf{err}^*(d_i,\rho _i,\delta _i,t_{i-1}+s)+\mathsf{err}^*(d_i/k_i,\rho _i,\delta _i,k_i)\).

• \(\epsilon ^{\mathsf{fin}}\leq {(1-\delta _M)}^{t_M}\).

Above, \({\mathsf{B}}^*\) and \({\mathsf{err}}^*\) are the proximity bound and error (respectively) described in Section 2.1.

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.

Let \(\mathcal{C}:= \mathrm{RS}[\mathbb {F},\mathcal{L},d]\) be a Reed-Solomon code with rate \(\rho :=\frac{d}{|\mathcal{L}|}\) and let \(B'(\rho ):=\sqrt{\rho }\). For every \(\delta \in (0,1 - B'(\rho ))\) and functions \(f_1,\ldots ,f_m : \mathcal{L}\to \mathbb {F}\), if

then there exists a subset \(S \subseteq \mathcal{L}\) with \(|S| \ge (1 - \delta )\cdot |L|\), and for every \(i \in [m]\), there exists \(u \in \mathrm{RS}[\mathbb {F},\mathcal{L},d]\) such that \(f_i(S) = u(S)\).

Above, \(\mathsf{err}'(d,\rho ,\delta ,m)\) is defined as follows:

• if \(\delta \in \left(0,\frac{1-\rho }{2}\right]\) then

  \[ \mathsf{err}'(d,\rho ,\delta ,m)=\frac{(m-1)\cdot d}{\rho \cdot |\mathbb {F}|} \]

• if \(\delta \in \Bigl(\frac{1-\rho }{2}, 1-\sqrt{\rho }\Bigr)\) then

  \[ \mathsf{err}'(d,\rho ,\delta ,m)=\frac{(m-1)\cdot {d}^2}{|\mathbb {F}|\cdot {\Bigl(2\cdot \min {1-\sqrt{\rho }-\delta ,\frac{\sqrt{\rho }}{20}}\Bigr)}^7} \]

Consider the following ingrediants:

• A security parameter \(\lambda \in \mathbb {N}\).

• A Reed-Solomon code \(\mathrm{RS}[\mathbb {F},\mathcal{L},d]\) with \(\rho :=\frac{d}{|\mathcal{L}|}\) where \(d\) is a power of \(2\), and \(\mathcal{L}\) is a smooth domain.

• A proximity parameter \(\delta \in (0,1-1.05\cdot \sqrt{\rho })\).

• A folding parameter \(k\in \mathbb {N}\) that is power of \(2\) with \(k\geq 4\).

If \(|\mathbb {F}|=\Omega (\frac{\lambda \cdot 2^\lambda \cdot d^2\cdot {|\mathcal{L}|}^2}{\log (1/\rho )})\), there is a public-coin IOPP for \(\mathrm{RS}[\mathbb {F},\mathcal{L},d]\) with the following parameters:

• Round-by-round soundness error \(2^{-\lambda }\).

• Round complexity: \(M:=O(\log _k{d})\).

• Proof length: \(|\mathcal{L}|+O_k(\log {d})\).

• Query complexity to the input: \(\frac{\lambda }{-\log {(1-\delta )}}\).

• Query complexity to the proof strings: \(O_k(\log {d}+\lambda \cdot \log {\Big(\frac{\log {d}}{\log {1/\rho }}\Big)})\).