Paper 2026/1903

Chosen-Block BAA Codes: Fast, Near the Gilbert–Varshamov Bound, and Field-Agnostic

Abstract

Block-Accumulate-Accumulate (BAA) codes provide fast encoding for pseudorandom correlation generators and code-based zero-knowledge. We replace their independently sampled local maps with repeated copies of one fixed short code. This chosen-block construction retains the two permutation-prefix-sum rounds while allowing the constituent code to be selected for distance and efficient implementation. Over $\mathbb{F}_2$, exact weight-distribution propagation gives finite-length distance guarantees. Suitable constituents yield numerical asymptotic distance estimates reaching $99.99\%$ of the Gilbert-Varshamov (GV) distance at rate $1/2$. Our practical binary instantiations encode about a million message symbols in $23$-$24$ ms on one CPU thread and under $6$ ms on $24$-$32$ threads. Over larger fields, we add random nonzero coordinate scalings and account for cancellations. For every field of size $q\ge2^{127}$, including $128$-bit prime fields, Reed-Solomon constituents certify relative distances $0.30$ and $0.60$ at rates $1/2$ and $1/4$, respectively. At message dimension $k=2^{20}$, each distance bound fails with probability below $2^{-137}$ under independent uniform sampling of the permutations and nonzero scalings. The rate-$1/4$ asymptotic distance estimate reaches $81\%$ of large-field GV. To investigate the gap between this estimate and GV, we identify permutation patterns that force low-weight codewords regardless of the nonzero coordinate scalings.