Paper 2024/1843

Khatam: Reducing the Communication Complexity of Code-Based SNARKs

Hadas Zeilberger, Yale University
Abstract

Every linear code satisfies the property of ``correlated agreement", meaning that if πL,πR are two vectors in Fn and if πL+rπR is close in Hamming distance to some codeword in C, then πL and πR each agree with a codeword in C in positions indexed by elements of S[n]. In this work, we prove something stronger -- that if πL+rπR is close to C, then πL,πR and (πL+rπR) all agree with codewords at positions indexed by elements of S, except with negligible probability over rF. Our result holds as long as |S|>(1ΔC+ϵ)1/3, and with failure probability smaller than 2ϵ2|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

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint.
Keywords
IOPPFRIProximity GapsSNARKs
Contact author(s)
hadas zeilberger @ yale edu
History
2025-02-20: last of 4 revisions
2024-11-09: received
See all versions
Short URL
https://ia.cr/2024/1843
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2024/1843,
      author = {Hadas Zeilberger},
      title = {Khatam: Reducing the Communication Complexity of Code-Based {SNARKs}},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/1843},
      year = {2024},
      url = {https://eprint.iacr.org/2024/1843}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.