Paper 2024/1843

Khatam: Reducing the Communication Complexity of Code-Based SNARKs

Abstract

Every linear code satisfies the property of ``correlated agreement", meaning that if $\pi_L, \pi_R$ are two vectors in $\mathbb{F}^{n}$ and if $\pi_L + r \pi_R$ is close in Hamming distance to some codeword in $C$, then $\pi_L$ and $\pi_R$ each agree with a codeword in $C$ in positions indexed by elements of $S \subset [n]$. In this work, we prove something stronger -- that if $\pi_L + r \pi_R$ is close to $C$, then $\pi_L, \pi_R$ and $(\pi_L + r \pi_R)$ all agree with codewords at positions indexed by elements of $S$, except with negligible probability over $r \leftarrow \mathbb{F}$. Our result holds as long as $|S| > (1 - \Delta_C + \epsilon)^{1/3}$, and with failure probability smaller than $\frac{2}{\epsilon^{2} |\mathbb{F}|}$. Furthermore, our results extend to any finite field and any linear code. We use this result to prove that BaseFold(Crypto 2024), an efficient multilinear polynomial commitment scheme, is secure in the \textit{list decoding regime}, which significantly reduces its communication complexity. Our result is agnostic with respect to both the field and code, and therefore can be used to reduce the communication complexity of a wide class of coding-based multilinear polynomial commitment schemes.

Note: - Corrected various errata - Prove security above the one-and-a-half Johnson bound, rather than the double Johnson bound