4 Various Papers 4.3 Schwartz-Zippel By Dana Moshkovitz 4.5 Interleaved Linear Code Testing with Logarithmic Randomness

4.4 Ligero Interleaved Linear Code Testing

For a code $C\subseteq\Sigma^{n}$ and a vector $\mathbf{v}\in\Sigma^{n}$ ,

•

denote by $d(\mathbf{v},C)$ the minimum distance of $\mathbf{v}$ from $C$ , namely the number of positions in which $\mathbf{v}$ differs from the closest codeword in $C$ ,
•

denote by $d(V,C)$ the minimum distance between a vector set $V$ and a code $C$ , that

$d(V,C)=\min_{\mathbf{v}\in V}d(\mathbf{v},C),$
•

denote by $\Delta(\mathbf{v},C)$ the set of positions in which $\mathbf{v}$ differs from such a closest codeword,
•

denote by $\Delta(V,C)$ the set of positions in which some $\mathbf{v}\in V$ differs from their closest codeword in $C$ , that

$\Delta(V,C)=\bigcup_{\mathbf{v}\in V}\Delta(\mathbf{v},C).$

Definition 4.4.1 (Interleaved Code).

Let $L\subset\mathbb{F}^{n}$ be an $[n,k,d]$ linear code over $\mathbb{F}$ . We let $L^{m}$ denote the $[n,mk,d]$ (interleaved) code over $\mathbb{F}^{m}$ whose codewords are all $\mathbf{U}\in\mathbb{F}^{m\times n}$ , such that each row $\mathbf{u}_{i}$ of $\mathbf{U}$ satisfies $\mathbf{u}_{i}\in L$ , and let $\mathbf{u}_{\ast,j}$ denote the $j^{\mathrm{th}}$ symbol (column) of $\mathbf{U}$ .

A randomized algorithm [AHI+17] to test the membership of $\mathbf{U}$ in $L^{m}$ follows, where $\mathbf{U}$ is stored in an oracle $\mathcal{O}$ :

•

$\mathcal{V}$ samples $\mathbf{r}\stackrel{{\scriptstyle\textsc{r}}}{{\leftarrow}}\mathbb{F}^{m}$ and sends over $\mathbf{r}$ to $\mathcal{P}$ .
•

$\mathcal{P}$ sends back $\mathbf{w}\leftarrow\mathbf{r}^{\mathsf{T}}\mathbf{U}$ to $\mathcal{V}$ .
•

$\mathcal{V}$ samples a set of positions $Q\stackrel{{\scriptstyle\textsc{r}}}{{\leftarrow}}[1,n]^{\ell}$ , and queries $\mathcal{O}$ for symbols $\mathbf{u}_{\ast,i}$ for all $i\in Q$ .
•

$\mathcal{V}$ checks if $\mathbf{w}$ is consistent with $\{\mathbf{u}_{\ast,i}\}_{i\in Q}$ by $\langle\mathbf{r},\mathbf{u}_{\ast,i}\rangle=w_{i}$ .

Lemma 4.4.2.

Let $e$ be a positive integer such that $e<d/4$ . Suppose $d(\mathbf{U}^{\ast},L^{m})>e$ , then for a random $\mathbf{w}^{\ast}$ in $\mathrm{RowSpan}(\mathbf{U}^{\ast})$ ,

\Pr\left[d\left(\mathbf{w}^{\ast},L\right)\leq e\right]\leq\frac{e+1}{\left|% \mathbb{F}\right|}.

Proof.

We introduce the following lemma, stating that if there is an element in the rowspan of $\mathbf{U}^{\ast}$ has large distance, then such element is almost everywhere in the rowspan space.

Lemma 4.4.3.

Suppose $\mathbf{u},\mathbf{v}\in\mathrm{RowSpan}\left(\mathbf{U}^{\ast}\right)$ with $d\left(\mathbf{u},L\right)>2e$ , then over the line $f(\alpha)=\alpha\cdot\mathbf{u}+\mathbf{v}$ where $\alpha\in\mathbb{F}$ ,

\Pr\left[d\left(\alpha\cdot\mathbf{u}+\mathbf{v},L\right)\leq e\right]\leq% \left|\mathbb{F}\right|^{-1}.

Proof.

On the line $f(\alpha)=\alpha\cdot\mathbf{u}+\mathbf{v}$ , suppose there are 2 distinct elements $f(\alpha_{0})$ and $f(\alpha_{1})$ , such that

d\left(\alpha_{0}\cdot\mathbf{u}+\mathbf{v},L\right)\leq e\text{ and }d\left(% \alpha_{1}\cdot\mathbf{u}+\mathbf{v},L\right)\leq e.

By triangle inequality,

d\left(\left(\alpha_{0}-\alpha_{1}\right)\cdot\mathbf{u},L\right)\leq d\left(% \alpha_{0}\cdot\mathbf{u}+\mathbf{v},L\right)+d\left(\alpha_{1}\cdot\mathbf{u}% +\mathbf{v},L\right)\leq 2e,

this contradicts against the assumption of $d(\mathbf{u},L)>2e$ . Hence, at most 1 element on $f(\alpha)$ has distance at most $e$ . ∎

Corollary 4.4.4.

Suppose $\mathbf{u}\in\mathrm{RowSpan}\left(\mathbf{U}^{\ast}\right)$ has $d\left(\mathbf{u},L\right)>2e$ , then for a random $\mathbf{w}^{\ast}$ in $\mathrm{RowSpan}\left(\mathbf{U}^{\ast}\right)$ ,

\Pr\left[d\left(\mathbf{w}^{\ast},L\right)\leq e\right]\leq\left|\mathbb{F}% \right|^{-1}.

Proof.

We foliate $\mathrm{RowSpan}\left(\mathbf{U}^{\ast}\right)$ with $\left|\mathbb{F}\right|^{m-1}$ parallel lines similar to [Mos10], where each line is defined by $\alpha\cdot\mathbf{u}+\mathbf{v}$ . By lemma 4.4.3, each line has at most 1 element of distance at most $e$ , and thus at most $\left|\mathbb{F}\right|^{m-1}$ such elements, which completes the proof. ∎

On the other hand, if every element in $\mathrm{RowSpan}\left(\mathbf{U}^{\ast}\right)$ has distance to $L$ at most $2e$ , fixing a differed position $j$ , we argue that there are at most 1 element over a line, with distance to $L$ is at most $e$ , and the element is not differed at $j$ .

Lemma 4.4.5.

Suppose $\mathbf{u},\mathbf{v}\in\mathrm{RowSpan}\left(\mathbf{U}^{\ast}\right)$ with $j\in\Delta\left(\mathbf{u},L\right)$ , then

\Pr\left[d\left(\alpha\cdot\mathbf{u}+\mathbf{v},L\right)\leq e\bigwedge j% \notin\Delta\left(\alpha\cdot\mathbf{u}+\mathbf{v},L\right)\right]\leq\left|% \mathbb{F}\right|^{-1}.

Proof.

If there are 2 distinct elements on $f(\alpha)$ both have the $j^{\mathrm{th}}$ symbol matched, and both distances to $L$ are at most $e$ , then by triangle inequality,

	$\displaystyle d\left(\mathrm{Span}\left(f(\alpha_{0}),f(\alpha_{1})\right),L\right)$	$\displaystyle=\min_{a,b}d\left(a\cdot f(\alpha_{0})+b\cdot f(\alpha_{1}),L\right)$
		$\displaystyle\leq d\left(\alpha_{0}\cdot\mathbf{u}+\mathbf{v},L\right)+d\left(% \alpha_{1}\cdot\mathbf{u}+\mathbf{v},L\right)$
		$\displaystyle\leq 2e<d/2,$

all elements in the $\mathrm{Span}\left(f(\alpha_{0}),f(\alpha_{1})\right)$ are in the unique decoding radius, hence all elements have $j^{\mathrm{th}}$ symbol matched. Yet this contradicts $\mathbf{u}\in\mathrm{Span}\left(f(\alpha_{0}),f(\alpha_{1})\right)$ , that $j\in\Delta(\mathbf{u},L)$ . Hence, there are at most 1 such element on the $f(\alpha)$ . ∎

The following corollary is immediate by the space foliation idea in [Mos10].

Corollary 4.4.6.

For a random $\mathbf{w}^{\ast}$ in $\mathrm{RowSpan}\left(\mathbf{U}^{\ast}\right)$ , and $j\in\Delta(\mathbf{U}^{\ast},L^{m})$ ,

\Pr\left[d(\mathbf{w}^{\ast},L)\leq e\bigwedge j\notin\Delta(\mathbf{w}^{\ast}% ,L)\right]\leq\left|\mathbb{F}\right|^{-1}.

Since $d(\mathbf{U}^{\ast},L^{m})>e$ , we union bound over at least $e+1$ differed positions, upper bounded by $(e+1)\cdot\left|\mathbb{F}\right|^{-1}$ . ∎

An improved result of distance preserving of random linear combination over linear code is also in [AHI+17].

Lemma 4.4.7.

Let $e$ be a positive integer such that $e<d/3$ . Suppose $d(\mathbf{U}^{\ast},L^{m})>e$ , then for a random $\mathbf{w}^{\ast}$ in $\mathrm{RowSpan}(\mathbf{U}^{\ast})$ ,

\Pr\left[d\left(\mathbf{w}^{\ast},L\right)\leq e\right]\leq\frac{e+1}{\left|% \mathbb{F}\right|}.

Proof.

We start by showing there exists elements in $\mathrm{RowSpan}\left(\mathbf{U}^{\ast}\right)$ such that the distance to $L$ greater than $e$ .

Lemma 4.4.8.

Suppose $d\left(\mathbf{U}^{\ast},L^{m}\right)>e$ , and $\left|\mathbb{F}\right|>e$ , then there exists $\mathbf{w}^{\ast}\in\mathrm{RowSpan}\left(\mathbf{U}^{\ast}\right)$ such that $d\left(\mathbf{w}^{\ast},L\right)>e$ .

Proof.

Suppose all $\mathbf{w}^{\ast}\in\mathrm{RowSpan}\left(\mathbf{U}^{\ast}\right)$ have $d\left(\mathbf{w}^{\ast},L\right)\leq e$ , then let $\mathbf{u}^{\ast}\in\mathrm{RowSpan}\left(\mathbf{U}^{\ast}\right)$ maximizes the distance to $L$ ,

\max_{\mathbf{v}^{\ast}\in\mathrm{RowSpan}(\mathbf{U}^{\ast})}d\left(\mathbf{v% }^{\ast},L\right)=d\left(\mathbf{u}^{\ast},L\right)\leq e.

There must exist another element $\mathbf{x}^{\ast}$ in the rowspan, such that

\Delta\left(\mathbf{x}^{\ast},L\right)\setminus\Delta\left(\mathbf{u}^{\ast},L% \right)\neq\varnothing,

otherwise $d\left(\mathbf{u}^{\ast},L\right)=d\left(\mathbf{U}^{\ast},L^{m}\right)>e$ , contradicting to the prior assumption of $d\left(\mathbf{u}^{\ast},L\right)\leq e$ .

We also want to know, if all $\mathbf{w}^{\ast}\in\mathrm{RowSpan}\left(\mathbf{U}^{\ast}\right)$ are of distance at most $e$ to $L$ , does the nearest codewords follow the same linear combination as the $\mathbf{w}^{\ast}$ ’s (or we cannot analyze by the union of differed positions).

Construct a line $f(\alpha)=\alpha\cdot\mathbf{u}^{\ast}+\mathbf{x}^{\ast}$ , and let $\mathbf{u},\mathbf{x},\mathbf{y}$ be the codewords within $e$ distance to $\mathbf{u}^{\ast},\mathbf{x}^{\ast},f(\alpha)$ , then

d\left(\alpha\cdot\mathbf{u}^{\ast}+\mathbf{x}^{\ast},\alpha\cdot\mathbf{u}+% \mathbf{x}\right)\leq d\left(\mathbf{u}^{\ast},\mathbf{u}\right)+d\left(% \mathbf{x}^{\ast},\mathbf{x}\right)\leq 2e,

the first inequality holds by the triangle inequality, and the second holds by the assumption that any element in the rowspan is of distance to $L$ at most $e$ . Then the distance between 2 valid codewords is

d\left(\alpha\cdot\mathbf{u}^{\ast}+\mathbf{x}^{\ast},\mathbf{y}\right)\leq d% \left(\alpha\cdot\mathbf{u}^{\ast}+\mathbf{x}^{\ast},f(\alpha)\right)+d\left(f% (\alpha),\mathbf{y}\right)\leq 2e+e<d,

which leads to a contradiction, as any 2 valid codewords are at least of $d$ distance. Hence, $\mathbf{y}=\alpha\cdot\mathbf{u}+\mathbf{x}$ .

Assuming all $\mathbf{w}^{\ast}\in\mathrm{RowSpan}\left(\mathbf{U}^{\ast}\right)$ have $d\left(\mathbf{w}^{\ast},L\right)\leq e$ , now we know the linear combination of $\mathbf{w}^{\ast}$ ’s is the same as the linear combination of the nearest $\mathbf{w}$ codewords. Let

\Delta_{\mathbf{u}^{\ast},\mathbf{x}^{\ast}}=\Delta\left(\mathbf{u}^{\ast},L% \right)\cap\Delta\left(\mathbf{x}^{\ast},L\right).

Then the probability for any position in $\Delta_{\mathbf{u}^{\ast},\mathbf{x}^{\ast}}$ being cancelled on a random $\alpha$ is at most $\left|\Delta_{\mathbf{u}^{\ast},\mathbf{x}^{\ast}}\right|\cdot\left|\mathbb{F}% \right|^{-1}$ by union bound. Hence, by

\left|\Delta_{\mathbf{u}^{\ast},\mathbf{x}^{\ast}}\right|<e<\left|\mathbb{F}% \right|,

first inequality holds by $d\left(\mathbf{u}^{\ast},L\right)<e$ , then the probability that no position in $\Delta_{\mathbf{u}^{\ast},\mathbf{x}^{\ast}}$ being cancelled is positive, which proves the existence of $\mathbf{w}^{\ast}$ that $d\left(\mathbf{w}^{\ast},L\right)>e$ . ∎

Since there exists elements in the rowspan such that the distance to $L$ is greater than $e$ , in order to strengthen the result from lemma 4.4.2, it suffices to show that in an affine subspace of $\mathbb{F}^{n}$ , either all points are of distances within $e$ to $L$ , or almost all are not. This reduces to showing the same in 1-dimensional space.

Lemma 4.4.9.

For any $\mathbf{u},\mathbf{v}\in\mathbb{F}^{n}$ constructing a line $\alpha\cdot\mathbf{u}+\mathbf{v}$ ,

•

either every points have $d\left(\alpha\cdot\mathbf{u}+\mathbf{v},L\right)\leq e$ ,
•

or at most $e$ points have $d\left(\alpha\cdot\mathbf{u}+\mathbf{v},L\right)\leq e$ .

Proof.

We show this with 2 vectors of Hamming weight at most $e$ , and see if any element in the 1-dimensional affine subspace can be within distance $e$ to any valid non-zero codeword. Let $\mathbf{u}^{\ast},\mathbf{v}^{\ast}$ be 2 vectors of Hamming weights at most $e$ , then they define a line $f(\alpha)=\alpha\cdot\mathbf{u}^{\ast}+\mathbf{v}^{\ast}$ . The lemma can be proved in 2 cases:

•

$\left|\mathrm{supp}\left(\mathbf{u}^{\ast}\right)\cup\mathrm{supp}\left(% \mathbf{v}^{\ast}\right)\right|\leq e$ . Then any element on the line are within distance $e$ to $\boldsymbol{0}$ .
•

$\left|\mathrm{supp}\left(\mathbf{u}^{\ast}\right)\cup\mathrm{supp}\left(% \mathbf{v}^{\ast}\right)\right|>e$ . The intersection $\Delta_{\mathbf{u}^{\ast},\mathbf{v}^{\ast}}$ has at most $e-1$ elements. By a similar argument of differed position cancelling in lemma 4.4.8, there are at most $e-1$ points on the line with overlapped disagreeing positions cancelled, hence there are at most $e-1$ points within distance $e$ to $\boldsymbol{0}$ .

Suppose there is a non-zero codeword $\mathbf{c}$ such that an $\alpha\cdot\mathbf{u}^{\ast}+\mathbf{v}^{\ast}$ is within distance $e$ to $\mathbf{c}$ , but by triangle inequality,

$d\left(\boldsymbol{0},\mathbf{c}\right)\leq d\left(\boldsymbol{0},\alpha\cdot% \mathbf{u}^{\ast}+\mathbf{v}^{\ast}\right)+d\left(\alpha\cdot\mathbf{u}^{\ast}% +\mathbf{v}^{\ast},\mathbf{c}\right)\leq d\left(\boldsymbol{0},\mathbf{v}^{% \ast}\right)+d\left(\boldsymbol{0},\mathbf{u}^{\ast}\right)+d\left(\alpha\cdot% \mathbf{u}^{\ast}+\mathbf{v}^{\ast},\mathbf{c}\right)\leq 3e<d,$

which is a contradiction. Hence, there is only $\boldsymbol{0}$ that is within $e$ distance to elements on the line.

∎

By lemma 4.4.8 and lemma 4.4.9, the proof for lemma 4.4.7 is immediate. ∎

We conclude with the soundness analysis, when $\mathbf{U}^{n}$ is far from $L^{m}$ .

Theorem 4.4.10.

Let $e<d/3$ be a positive integer. Suppose $d(\mathbf{U}^{\ast},L^{m})>e$ , then for any malicious $\mathcal{P}$ strategy, $\mathcal{V}$ accepts with probability at most

\left(1-\frac{e+1}{n}\right)^{t}+\frac{e+1}{\left|\mathbb{F}\right|}.

Proof.

Let $\mathbf{w}^{\ast\mathsf{T}}=\mathbf{r}^{\mathsf{T}}\mathbf{U}^{\ast}$ , the probability upper bound follows:

	$\displaystyle\Pr\left[\mathcal{V}\text{ accepts}\right]$	$\displaystyle\leq\Pr\left[\mathcal{V}\text{ accepts}\mid d\left(\mathbf{w}^{% \ast},L\right)>e\right]+\Pr\left[d\left(\mathbf{w}^{\ast},L\right)\leq e\right]$
		$\displaystyle\leq\binom{n-e-1}{t}\cdot\binom{n}{t}^{-1}+\frac{e+1}{\left\|% \mathbb{F}\right\|}$
		$\displaystyle\leq\left(1-\frac{e+1}{n}\right)^{t}+\frac{e+1}{\left\|\mathbb{F}% \right\|},$

the first inequality holds by 1.4.14 trick, while the second holds by lemma 4.4.7. ∎