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^{\ast }\in \mathbb{N}$, shifting parameter $r\in \mathbb{F}$, functions $f_1,\dots ,f_m:\mathcal{L}\to \mathbb{F}$, and degrees $0\le d_1,\dots ,d_m\le d^{\ast }$, we define $\mathsf{Combine}(d^{\ast },r,(f_1,d_1),\dots ,(f_m,d_m)):\mathcal{L}\to \mathbb{F}$ as follows:

Above, $r_1:=1$, $r_i:=r^{i-1+\sum _{j<i}(d^{\ast }-d_i)}$ for $i>1$.

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

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

Let $f:\mathcal{L}\to \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}}^{<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}\to \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}}^{<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}}^{<d}[X]$ be a polynomial and $S\subseteq \mathbb{F}$ be a set, let ${\hat{V}}_S\in {\mathbb{F}}^{<|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}}^{<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\to \mathbb{F}$ be functions. Let $\widehat{\mathsf{Ans}}\in {\mathbb{F}}^{<|S|}[X]$ be the (unique) polynomial with $\widehat{\mathsf{Ans}}(x)=\mathsf{Ans}(x)$ for every $x\in S$, and let ${\hat{V}}_S\in {\mathbb{F}}^{<|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}(f,S,\mathsf{Ans},\mathsf{Fill}):\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}{|\mathcal{L}|}$.

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}}^{<d}[X]$ to denote a nearest polynomial to $f$ on $\mathcal{L}$ (breaking ties arbitrarily).

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

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

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

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

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

Let $f:\mathcal{L}\to \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}\to \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|<d$, and $\mathsf{Ans},\mathsf{Fill}:S\to \mathbb{F}$ are functions. Suppose that for every $u\in \mathsf{List}(f,d,\delta )$ there exists $x\in S$ with $\hat{u}(x)\ne \mathsf{Ans}(x)$. Then

where $T:=\{x\in \mathcal{L}\cap S:\widehat{\mathsf{Ans}}(x)\ne f(x)\}$.

Consider $(\mathbb{F},M,d,k_0,\dots ,k_M,{\mathcal{L}}_0,\dots ,{\mathcal{L}}_M,t_0,\dots ,t_M)$ and $d_0,\dots ,d_M$ as in Construction 3.2, and for every $0\le i\le 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,\dots ,{\delta }_M$ where

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

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

• for every $0<i\le 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 $({ϵ}^{\mathsf{fold}},{ϵ}_1^{\mathsf{out}},{ϵ}_1^{\mathsf{shift}},\dots ,{ϵ}_M^{\mathsf{out}},{ϵ}_M^{\mathsf{shift}},{ϵ}^{\mathsf{fin}})$ where:

• ${ϵ}^{\mathsf{fold}}\le {\mathsf{err}}^{\ast }(d_0/k_0,{\rho }_0,{\delta }_0,k_0)$.

• ${ϵ}_i^{\mathsf{out}}\le \frac{l_i^2}{2}\cdot {(\frac{d_i}{|\mathbb{F}|-|{\mathcal{L}}_i|})}^s$

• ${ϵ}_i^{\mathsf{shift}}\le {(1-{\delta }_{i-1})}^{t_{i-1}}+{\mathsf{err}}^{\ast }(d_i,{\rho }_i,{\delta }_i,t_{i-1}+s)+{\mathsf{err}}^{\ast }(d_i/k_i,{\rho }_i,{\delta }_i,k_i)$.

• ${ϵ}^{\mathsf{fin}}\le {(1-{\delta }_M)}^{t_M}$.

Above, ${\mathsf{B}}^{\ast }$ and ${\mathsf{err}}^{\ast }$ 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^{\prime }(\rho ):=\sqrt{\rho }$. For every $\delta \in (0,1-B^{\prime }(\rho ))$ and functions $f_1,\dots ,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}}^{\prime }(d,\rho ,\delta ,m)$ is defined as follows:

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

  $${\mathsf{err}}^{\prime }(d,\rho ,\delta ,m)=\frac{(m-1)\cdot d}{\rho \cdot |\mathbb{F}|}$$

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

  $${\mathsf{err}}^{\prime }(d,\rho ,\delta ,m)=\frac{(m-1)\cdot d^2}{|\mathbb{F}|\cdot {(2\cdot min1-\sqrt{\rho }-\delta ,\frac{\sqrt{\rho }}{20})}^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\ge 4$.

If $|\mathbb{F}|=\mathrm{\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 (\frac{\log d}{\log 1/\rho }))$.