Welcome to the resource topic for 2025/2010
Title:
On the Distribution of the Distances of Random Words
Authors: Benjamin E. Diamond, Angus Gruen
Abstract:For each positive integer c^*, we construct an infinite sequence of Reed–Solomon codes C \subset \mathbb{F}_q^n, together with ball radii z, for which the proportion of \mathbb{F}_q^n collectively covered by the radius-z Hamming balls decays asymptotically more slowly than \frac{n^{c^*}}{q} does. To pinpoint this decay rate, we develop various new, sharp combinatorial estimates, pertaining to the volumes of balls and their intersections.
Our result proves that the capacity conjecture of Ben-Sasson, Carmon, Ishai, Kopparty and Saraf (J. ACM ‘23) is false. Our code families’ relative rates converge to 0 and their relative radii converge to 1. We suggest avenues by the means of which the capacity conjecture might be resuscitated; roughly, we suggest that that conjecture be restricted to the case of families whose relative rates are bounded from below by a positive constant. Our work shows that many deployed SNARKs may be less secure than they were formerly—optimistically—assumed to be.
ePrint: https://eprint.iacr.org/2025/2010
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 .