(SOLVED) Proximity Gaps up to Unique Decoding

See solution: Counterexample to a proximity gap conjecture.

(Liam Eagen)

https://eprint.iacr.org/2023/630

Conjecture 2.4 extending theorem 2.1

Motivation

In many SNARKs, we arrange our witness into columns. In code based SNARKs (informally STARKs), each of these columns is encoded using an error correcting code. The proof shows that each of these columns is sufficiently close to the code using a proximity test like FRI. Rather than showing this separately for each column, we would like to be able to batch the proximity tests. To do this, we would like to be able to argue something like: If a random linear combination of the columns is close to the code, then each column is itself close to the code with high probability. Then we could run the proximity test once on the linear combination.

Proximity Gaps

We say that a set $S$ exhibits a proximity gap with respect to a property $\phi$ if either

1. nearly all $x \in S$ satisfy $\phi(x)$
2. nearly all $x \in S$ satisfy $\neg \phi(x)$

As an example, consider the set of all values of a degree $k$ polynomial $S = \{ f(x) : x \in \mathbb{F} \}$ and the property $\phi(x) = \top$ if $f(x) = 0$. Either, $f(X) = 0$ identically, in which case all $f(x) = 0$, or there are at most $k$ places where $f(x) = 0$ independent of the size of the field.

Note this property is used to construct SNARKs; we can show that a polynomial of low degree is identically zero by testing it at a random point.

Codes

For codes $C$ , we are interested in the set $S$ of points on a line $\ell(X) = (1 - X) \ell_0 + X \ell_1$, the property $\phi(x) = \top$ if $x$ is $e$-close to the code for some proximity parameter $e$, and the number of cases where the property does not hold $f$.

For various families of codes and parameters $(e, f)$, proximity gaps are known. Ben-Sasson et al showed that Reed Solomon codes of length $n$, dimension $k$, and distance $d = n - k + 1$ exhibit a proximity gap for $(d/2, n)$ (up to unique decoding) as well as another one up to the Johnson bound. For general linear codes $C = [n,k,d]_q$, [AHIV23] showed that they exhibit a proximity gap $(e, e+1)$ for all $e < d/3$. See the linked paper at the top for a proof.

Problem

The problem is to extend this result of [AHIV23] up to the unique decoding radius for arbitrary linear codes. Note that this would be an improvement over Ben Sasson et al. Partial credit will be awarded for any improvement over the current state of the art or a counter example.

Statement

Let $C = [n,k,d]_q$ be a linear code of length $n$, dimension $k$, and distance $d$ over a field $\mathbb{F}_q.$ Suppose we have two points $\ell_0, \ell_1 \in \mathbb{F}^n_q$ and let $\ell(X) = (1-X) \ell_0 + X \ell_1$ the line between these two points. Let $e$ be the proximity parameter any value $e < d/2$.

If there exist more than $e+1$ points $t_1, ..., t_{e+1}$ on the line that are $e$ close to the code, i.e. $\Delta(\ell(t_i), C) \leq e$, then all points on the line are $e$ close to the code.