Paper 2026/524

Distance of RAA Codes over Large Finite Fields (with Applications in zkSNARKs and PCGs)

Abstract

Error-correcting codes play a central role in modern cryptography, enabling efficient constructions of primitives such as zero knowledge proofs and secure multiparty computations. Among them, repeat-accumulate-accumulate (RAA) codes have recently attracted significant attention due to their linear-time encoding and good distance properties. However, prior work only established provable distance guarantees over the binary field or over finite fields whose size is smaller than the message length. The underlying techniques do not extend to larger fields. This restriction is significant, as many cryptographic constructions based on error-correcting codes operate over large finite fields. In this paper, we prove that RAA codes achieve constant relative distance $0<\delta\le \frac{1}{2}$ with high probability over large finite fields. Moreover, we resolve an open conjecture by showing for the first time that the distance of RAA codes improves over large fields. We provide both theoretical analysis and empirical evidence demonstrating that, compared to the binary case, large fields yield strictly better distance guarantees with much smaller failure probabilities. Our empirical evaluation shows that for message length $n=2^{15}$ and repetition factor $r=4$, the RAA code over a 31-bit prime field achieves relative distance $1/2$, except with failure probability $2^{-16}$. This is better than the best provable distance of $\delta = 0.2$ with failure probability $2^{-7}$ over the binary field. Leveraging our improved distance bounds, we obtain a 2.6$\times$ reduction in the proof size of a polynomial commitment scheme based on RAA codes compared to using the binary-field bound, and a 5.4$\times$ reduction compared to a prior construction based on expand-accumulate codes.