Paper 2025/2010
On the Distribution of the Distances of Random Words
Angus Gruen, Zero Latency Labs
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.
BibTeX
@misc{cryptoeprint:2025/2010,
author = {Benjamin E. Diamond and Angus Gruen},
title = {On the Distribution of the Distances of Random Words},
howpublished = {Cryptology {ePrint} Archive, Paper 2025/2010},
year = {2025},
url = {https://eprint.iacr.org/2025/2010}
}