2 Tools for Reed-Solomon codes

2.1 Random linear combination as a proximity generator

Theorem 2.1

✓

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

\[ \Pr _{r\leftarrow \mathbb {F}}\! \Bigl[ \Delta \Bigl(\sum _{j=1}^m r^{j - 1}\cdot {f_j},\mathrm{RS}[\mathbb {F},\mathcal{L},d]\Bigr) \le \delta \Bigr]{\gt}\mathsf{err}'(d,\rho ,\delta ,m), \]

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} \]

2.2 Univariate Function Quotienting

In the following, we start by defining the quotient of a univariate function.

Definition 2.2

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:

\[ \forall x \in \mathcal{L},\quad \mathsf{Quotient}\bigl(f,S,\mathsf{Ans},\mathsf{Fill}\bigr)(x) := \begin{cases} \mathsf{Fill}(x) & \text{if } x \in S \\[6pt] \dfrac {f(x) - \hat{\mathsf{Ans}}(x)}{\hat{V}_S(x)} & \text{otherwise} \end{cases} \]

Next we define the polynomial quotient operator, which quotients a polynomial relative to its output on evaluation points. The polynomial quotient is a polynomial of lower degree.

Definition 2.3

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:

\[ \mathsf{PolyQuotient}(\hat{f},S)(X):=\frac{\hat{f}(X)-\hat{\mathsf{Ans}}(X)}{\hat{V}_S(X)} \]

The following lemma, implicit in prior works, shows that if the function is “quotiented by the wrong value”, then its quotient is far from low-degree.

Lemma 2.4

✓

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

\[ \Delta (\mathsf{Quotient}(f,S,\mathsf{Ans},\mathsf{Fill}),\mathrm{RS}[\mathbb {F},\mathcal{L},d-|S|])+\frac{|T|}{|\mathcal{L}|}{\gt}\delta , \]

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

2.3 Out of domain sampling

Lemma 2.5

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

\begin{align*} \Pr _{r_1,\ldots ,r_s\gets \mathbb {F}\setminus \mathcal{L}}[\exists \text{ distinct }u,u’\in \mathsf{List}(f,d,\delta ):\forall i\in [s],\hat{u}(r_i)=\hat{u}’(r_i)] & \leq \binom {l}{2}\cdot {\Big(\frac{d-1}{|\mathbb {F}|-|\mathcal{L}|}\Big)}^s \\ & \leq \Big(\frac{l^2}{2}\Big)\cdot {\Big(\frac{d}{|\mathbb {F}|-|\mathcal{L}|}\Big)}^s \end{align*}

2.4 Folding univariate functions

STIR relies on \(k\)-wise folding of functions and polynomials - this is similar to prior works, although presented in a slightly different form. As shown below, folding a function preserves proximity from the Reed-Solomon code with high probability.

The folding operator is based on the following fact, decomposing univariate polynomials into bivariate ones.

Fact 2.6

Given a polynomial \(\hat{q}\in \mathbb {F}[X]\):

For every univariate polynomial \(\hat{f}\in \mathbb {F}[X]\), there exists a unique bivariate polynomial \(\hat{Q}\in \mathbb {F}[X,Y]\) with \(\mathsf{deg}_X(\hat{Q}):=\lfloor {\mathsf{deg}(\hat{f})}/{\mathsf{deg}(\hat{q})}\rfloor \) and \(\mathsf{deg}_Y(\hat{Q}){\lt}\mathsf{deg}(\hat{q})\) such that \(\hat{f}(Z)=\hat{Q}(\hat{q}(Z),Z)\). Moreover \(\hat{Q}\) can be computed efficiently given \(\hat{f}\) and \(\hat{q}\). Observe that if \(\mathsf{deg}(\hat{f}){\lt}t\cdot \mathsf{deg}(\hat{q})\) then \(\mathsf{deg}(\hat{Q}){\lt}t\).
For every \(\hat{Q}[X,Y]\) with \(\mathsf{deg}_X(\hat{Q}){\lt}t\) and \(\mathsf{deg}_Y(\hat{Q}){\lt}\mathsf{deg}(\hat{q})\), the polynomial \(\hat{f}(Z)=\hat{Q}(\hat{q}(Z),Z)\) has degree \(\mathsf{deg}(\hat{f}){\lt}t\cdot \mathsf{deg}(\hat{q})\).

Below, we define folding of a polynomial followed by folding of a function.

Definition 2.7

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

Definition 2.8

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.

\[ \mathsf{Fold}(f,k,\alpha ):=\hat{p}_x(\alpha ). \]

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

The following lemma shows that the distance of a function is preserved under folding. If a functions \(f\) has distance \(\delta \) to a Reed-Solomon code then, with high probability over the choice of folding randomness, its folding also has a distance of \(\delta \) to the “\(k\)-wise folded” Reed-Solomon code.

Lemma 2.9

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}|}\),

\[ \Pr _{r^{\mathsf{fold}}\gets \mathbb {F}}[\Delta (\mathsf{Fold}[f,k,r^{\mathsf{fold}}],\mathrm{RS}[\mathbb {F},{\mathcal{L}}^k, d/k]){\lt}\delta ]{\gt}\mathsf{err}^*(d/k,\rho ,\delta ,k). \]

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

2.5 Combine functions of varying degrees

We show a new method for combining functions of varying degrees with minimal proximity require- ments using geometric sums. We begin by recalling a fact about geometric sums.

Fact 2.10

Let \(\mathbb {F}\) be a field, \(r\in \mathbb {F}\) be a field element, \(a\in \mathbb {N}\) be a natural number. Then

\[ \sum _{i=0}^{a}r^i:= \begin{cases} \Big(\frac{1-r^{a+1}}{1-r}\Big) & r\neq 1 \\ a+1 & r=1 \end{cases} \]

Definition 2.11

✓

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:

\begin{align*} \mathsf{Combine}({d}^*,r,(f_1,d_1),\ldots ,(f_m,d_m))(x)& :=\sum _{i=1}^{m}r_i\cdot f_i(x)\cdot \Big(\sum _{l=0}^{d^*-d_i}{(r\cdot x)}^l\Big) \\ & = \begin{cases} \sum _{i=1}^{m}r_i\cdot f_i(x)\cdot \Big(\frac{1-{(xr)}^{d^*-d_i+1}}{1-xr}\Big) & x\cdot r\neq 1\\ \sum _{i=1}^{m}r_i\cdot f_i(x)\cdot (d^*-d_i+1) & x\cdot r= 1 \end{cases}\end{align*}

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

Definition 2.12

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.

\[ \mathsf{DegCor}(d^*,r,f,d)(x):=f(x)\cdot \Bigg(\sum _{i=0}^{m}{(r\cdot x)}^l\Bigg)= \begin{cases} f(x)\cdot \frac{1-{(xr)}^{d^*-d_i+1}}{1-xr} & x\cdot r\neq 1\\ f(x)\cdot (d^*-d_i+1) & x\cdot r= 1 \end{cases} \]

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

Below it is shown that combining multiple polynomials of varying degrees can be done as long as the proximity error is bounded by \((\min {\{ 1-{\mathsf{B}}^*(\rho ),1-\rho -1/|\mathcal{L}|\} })\).

Lemma 2.13

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

\[ \Pr _{r\gets \mathbb {F}}[\Delta (\mathsf{Combine}(d^*,r,(f_1,d_1),\ldots ,(f_m,d_m)),\mathrm{RS}[\mathbb {F},\mathcal{L},d^*])]{\gt}\mathsf{err}^*(d^*,\rho ,\delta ,m\cdot (d^*+1)-\sum _{i=1}^{m}d_i), \]

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

\[ \forall i\in [m],\exists u\in \mathrm{RS}[\mathbb {F},\mathcal{L},d_i], f_i(S)=u(S). \]

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.