Welcome to the resource topic for 2024/1843
Title:
Khatam: Reducing the Communication Complexity of Code-Based SNARKs
Authors: Hadas Zeilberger
Abstract:We prove that Basefold(Crypto 2024) is secure in the \textit{list decoding regime}, within the double Johnson bound and with error probability \frac{O(n)}{|F|}. At the heart of this proof is a new, stronger statement for \textit{correlated agreement}, which roughly states that if a linear combination of vectors \pi_L + r \pi_R agrees with a codeword at every element in S \subset [n], then so do \pi_L, \pi_R. Our result is purely combinatorial and therefore extends to any finite field and any linear code. As such, it can be applied to any coding-based multilinear Polynomial Commitment Scheme to reduce its communication complexity.
ePrint: https://eprint.iacr.org/2024/1843
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .