How good are random quasi-abelian codes?
The minimum-distance bound that silent secure computation over small fields is waiting on, in the one asymptotic regime nobody can reach
Motivation
Pseudorandom correlation generators let two parties expand short seeds into large amounts of correlated randomness with no interaction, and they are what makes “silent” secure computation practical. Their security rests on the hardness of decoding a structured code, and the structure is chosen for a very specific algebraic reason: in a group algebra \(\mathbb{F}_q[G]\) the product of two sparse elements is sparse, so a sparse-error assumption survives multiplication, and fast transforms exist for suitable \(G\). That is why the line moved from quasi-cyclic to quasi-abelian codes, and why groups such as \((\mathbb{Z}/3\mathbb{Z})^{d}\) — which give OLE correlations over small fields — are the interesting ones rather than the cyclic groups the coding-theory literature has studied most.
Security against the attacks anyone knows how to mount is then one combinatorial fact away. Essentially all known attacks on LPN-style and syndrome-decoding-style assumptions are linear tests, and resistance to every linear test follows once a random code from the family has large minimum distance with high probability. So the cryptographic question reduces to a coding-theory question, and the coding-theory question is answered — in the wrong asymptotic regime.
Provenance and history
Maxime Bombar, Geoffroy Couteau, Alain Couvreur and Clément Ducros, Correlated Pseudorandomness from the Hardness of Quasi-Abelian Decoding (IACR ePrint 2023/845, CRYPTO 2023), introduce the quasi-abelian syndrome decoding problem and the PCG template built on it, and set out the distance question with both regimes side by side.
Fan and Lin proved that random quasi-\(G\) codes meet the Gilbert-Varshamov bound when the index \(\ell\) grows and \(G\) is fixed — including the modular case where \(\mathrm{char}(\mathbb{F}_q)\) divides \(|G|\) — by representation-theoretic means. The convergence exponent depends on \(|G|\), and cryptographic parameters have \(k\) and \(\ell\) small and \(|G|\) large, so this is the regime that does not apply.
In the regime that does, the picture is older and thinner. Kasami gave a Gilbert-Varshamov-like bound for rate-\(1/2\) quasi-cyclic codes in 1974; Gaborit and Zémor showed in 2006 that random double-circulant codes asymptotically satisfy a logarithmic improvement on it. Both are cyclic. The source conjectures the extension to arbitrary abelian groups and says the development is out of reach of the article.
There is a caveat that is part of the statement rather than a footnote. A syndrome lies in the ideal generated by the blocks of the parity-check matrix, and when that ideal is not the whole ring the distribution is biased — an effect invisible over large fields, where the blocks are invertible with overwhelming probability, and real over small ones. Enforcing the systematic form removes it, and the source’s belief that the distance stays linear once it is removed is explicitly labelled heuristic.
Progress arrived in August 2026. Li, Liu, Xing, Yao and Yuan (IACR ePrint 2026/939) give concrete non-asymptotic distance bounds for random quasi-abelian codes of rank \(1\) and index \(c\) over \(\mathbb{F}_p[(\mathbb{Z}/2\mathbb{Z})^{n}]\) with \(p\) an arbitrarily large prime, reaching the Gilbert-Varshamov bound up to an additive gap \(n/(c\log_2 p)\) — good enough to beat Spielman’s code substantially in a SNARK application — and note the argument generalises to \(\mathbb{F}_q[(\mathbb{Z}/d\mathbb{Z})^{n}]\) for \(d \mid q-1\) and to a generic \(\mathbb{F}[G]\) for a concrete \(G\). They also state that their bound is vacuous as \(|G| \to \infty\) and that the asymptotic question remains open, restating the conjecture as unresolved.
Parameter lattice
Minimum distance of random quasi-\(G\) codes, by asymptotic regime and group.
| \(G\) cyclic | \(G\) arbitrary abelian | |
|---|---|---|
| \(\ell \to \infty\), \(G\) fixed | Fan–Lin (special case) | Fan–Lin, meets GV, exponent depends on \(|G|\) |
| \(|G| \to \infty\), \(k,\ell\) fixed | Kasami; Gaborit–Zémor, GV plus a log improvement | c/0105 — open |
| \(|G| = 2^n\) fixed, \(p\) large, concrete | unstated | Li–Liu–Xing–Yao–Yuan, GV up to \(n/(c\log_2 p)\) |
| \(G\) trivial (plain linear codes) | Pierce, meets GV | same |
What each row buys: only the second row of the second column gives linear-test security for the small-field groups the PCG constructions actually want.