Paper 2024/1843

Khatam: Proximity Gaps For Multilinear Evaluation For All Linear Codes

Abstract

Two techniques have recently emerged in the construction of Succinct Non-Interactive Arguments of Knowledge (SNARKs) that yield extremely fast provers; The use of multilinear (instead of univariate) polynomial commitment schemes (PCS) and the construction of practical SNARKs from error-correcting codes. Recently, BaseFold (Crypto 2024) introduced a family of SNARKs that combine these two techniques, thereby achieving a better trade-off between prover time and verifier costs than prior work. Despite its impressive overall efficiency, BaseFold suffered from larger proof sizes than its univariate counterparts, due to unproven claims about linear codes, which were not relevant in the univariate setting. This work closes this gap by proving a new fact about linear codes -- that if $\pi_L, \pi_R$ are two vectors in $\mathbb{F}^{n}$ and if $\pi_L + r \pi_R$ is close to a codeword in $C$, then $\pi_L, \pi_R$ and $(\pi_L + r \pi_R)$ all agree with codewords at positions in the same set $S \subset [n]$, except with negligible probability over $r \leftarrow \mathbb{F}$. Our result holds as long as $|S| > ((1 - \Delta_C + \epsilon)^{1/3} + \eta) n$, for $\epsilon, \eta \in [0,1]$ and with failure probability smaller than $\frac{3}{\epsilon\eta |\mathbb{F}|}$, where $\Delta_C$ is the minimum distance of the code. Importantly, our results extend to any finite field and any linear code, and lead to a $2 \times$ reduction in proof size compared to state-of-the-art field-agnostic, hash-based SNARKs.

Note: - Fixed small errata and reorganized proofs - Rewrote technical overview and related work sections