Random Quasi-Abelian Codes Meet the Gilbert-Varshamov Bound as the Group Grows
Statement: AI-written, not yet formalized. Proof: open – no attempt yet.
Silent secure computation runs on pseudorandom correlation generators, and those rest on the hardness of decoding a structured code — here a quasi-abelian code over a group algebra. Essentially every known attack on such assumptions is a linear test, and resistance to all linear tests reduces to one purely combinatorial fact: a random code from the family has large minimum distance. Two asymptotic regimes are available. Fix the group and let the number of blocks grow, and the fact is a theorem of Fan and Lin. Let the group itself grow — the regime the cryptographic parameters actually live in — and it is a theorem only when the group is cyclic, due to Gaborit and Zémor. The conjecture is that the cyclic restriction can be dropped.
View PDF · LaTeX source · Formal statement — not yet formalized
The objects. For a finite abelian group \(G\), the group algebra \(\mathbb{F}_q[G]\) is the \(\mathbb{F}_q\)-vector space with basis \(G\), multiplied by the group law. An \(\mathbb{F}_q[G]\)-submodule of \((\mathbb{F}_q[G])^{\ell}\) is a quasi-\(G\) code of index \(\ell\); for cyclic \(G\) these are quasi-cyclic codes, for trivial \(G\) all linear codes. A quasi-\(G\) code of rank \(k\) is the row space of \(\Gamma \in (\mathbb{F}_q[G])^{k \times \ell}\), systematic when \(\Gamma = (I_k \mid \Gamma')\). As a code over \(\mathbb{F}_q\) its length is \(\ell \cdot |G|\) and its rate is \(r = k/\ell\).
Why distance is the whole question. The quasi-abelian syndrome decoding problem QA-SD generalises both plain and quasi-cyclic syndrome decoding — the latter underpinning the NIST round-4 submissions BIKE and HQC. In the linear test framework, which covers essentially all known attacks, resistance follows once the code generated by the parity-check matrix has large minimum distance with high probability.
The two regimes, and which one is a theorem. Fan and Lin (the source’s Theorem 20): for fixed abelian \(G\) and random quasi-\(G\) codes of index \(\ell \to \infty\) and rate \(r\), the relative minimum distance exceeds \(\delta\) with probability tending to \(1\) when \(r < 1 - h_q(\delta)\) and to \(0\) when \(r > 1 - h_q(\delta)\), both exponentially fast. But the source records the mismatch: “the exponent depends on \(|G|\): the larger the group \(G\), the higher this probability” — and cryptographic parameters have \(k\) and \(\ell\) small, often \(k=1\) with \(\ell\) a small constant, and \(|G|\) large. In that regime the statement is a theorem only for cyclic \(G\): Kasami gave a Gilbert-Varshamov-like bound for rate-\(1/2\) quasi-cyclic codes and Gaborit and Zémor showed random double-circulant codes asymptotically satisfy a logarithmic improvement on it.
Conjecture. Fix \(q\), constants \(k < \ell\) with \(r = k/\ell\), and \(\delta \in (0,1-1/q)\) with \(r < 1 - h_q(\delta)\). For any family of finite abelian groups with \(|G| \to \infty\), a random systematic quasi-\(G\) code of rank \(k\) and index \(\ell\) over \(\mathbb{F}_q\) has minimum distance greater than \(\delta \cdot \ell \cdot |G|\) with probability tending to \(1\).
How the source states it, and what this page supplies. Page 9: “We conjecture an extension of Gaborit and Zémor result to arbitrary abelian groups. The latter conjecture entails that the QA-SD problem cannot be broken by any attack from the linear test framework, for any choice of the underlying group \(G\).” Page 20: “Actually, to assert the resistance of QA-SD against linear attacks, it would be more relevant to consider the regime where \(k, \ell\) are constant and \(|G|\) goes to infinity as it is done in [GZ06] but such a development is out of reach of this article and we leave it as a conjecture.”
The source prints no formal statement, so the formalisation above is this page’s reading, and it makes two choices. It asks for the plain Gilbert-Varshamov threshold rather than the logarithmic improvement Gaborit and Zémor actually prove for double-circulant codes — the weaker target, because that is what the linear-test reduction needs. And it fixes the systematic form, for the reason below. A proof of the stronger form, or a proof for a restricted family of abelian groups, is progress and should be reported as such.
The systematic form is part of the statement, not decoration. A syndrome \(s = a_1e_1 + a_2e_2\) lies in the ideal \((a_1,a_2) \subseteq \mathbb{F}_q[G]\), and “when this ideal is not the full ring, there is an obvious bias”. Over a large field the blocks are invertible with overwhelming probability; over a small field they need not be, and in the growing-\(|G|\) regime that is exactly the failure mode. The source: “In this case, the minimum distance could drop, but heuristically a random quasi-\(G\) code will have a minimum distance linear in its length as long as this bias is removed, which is the case in our setting since we enforce the systematic form.” Note heuristically: that sentence is the source’s reason for believing the conjecture, not an argument for it.
View PDF — no proof written yet · LaTeX source — no proof written yet · Formal proof — not yet formalized
Open, with substantial recent progress that stops just short.
What was proved in 2026. Li, Liu, Xing, Yao and Yuan give a fine-grained analysis of the minimum distance of random quasi-abelian codes of rank \(1\) and index \(c\) over \(\mathbb{F}_p[(\mathbb{Z}/2\mathbb{Z})^{n}]\) for arbitrarily large prime fields, attaining the Gilbert-Varshamov bound up to an additive gap \(n/(c \log_2 p)\). Concretely: relative distance at least \(0.4142\) at rate \(1/2\) over a \(128\)-bit field with \(|G| = 2^{20}\), against \(0.1\) for Spielman’s code under the state-of-the-art analysis. They 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 group \(G\).
Why that does not settle it, in their words. “While we can obtain a concretely high minimum distance from Theorem 1.1, it remains open whether QA code is asymptotically good for fixed index \(c\) and field size \(p\), as our lower bound is meaningless when \(|G| = N \to \infty\).” They also restate the source’s conjecture explicitly as still open: “in [BCCD23] the authors conjectured that Gaborit and Zémor’s argument can be extended to arbitrary abelian groups and thus QA code approaches GV bound with \(|G|\) going to infinity.”
So the position on 2026-08-28 is: concrete non-asymptotic bounds for particular groups over large fields; no asymptotic statement for growing \(|G|\) beyond the cyclic case; and the general conjecture untouched.
What a proof would have to supply. An argument that survives \(|G| \to \infty\) with \(k\), \(\ell\) and \(q\) fixed, for an arbitrary abelian group. The Fan–Lin route is representation-theoretic and its exponent degenerates in this regime; the Gaborit–Zémor route uses double-circulant structure that an arbitrary abelian group does not have.
Why the choice of group has to be free. The point of moving from quasi-cyclic to quasi-abelian codes is that groups such as \((\mathbb{Z}/3\mathbb{Z})^{d}\) give a ring in which sparse elements multiply to sparse elements and fast transforms exist, which is what lets pseudorandom correlation generators produce OLE correlations over small fields. Without the conjecture, resistance to linear tests is established only for those groups where a distance bound happens to be available — and those are not the interesting ones.
Hardness itself is not what is in doubt. Decoding a random quasi-abelian code “ha[s] been studied for over 50 years by the coding theory community and to this day, no efficient algorithm is known”, and the problem is listed as open in the 2021 Encyclopedia of Coding Theory. What is missing is the distance bound that turns that belief into a linear-test guarantee.
Relation to c/0086. The expand-accumulate hub asks a minimum-distance question about a different code family over arbitrary rings. Same shape of obstacle — a distance bound is what a linear-test security argument needs — different family, different techniques. No implication either way.
What a reviewer should be suspicious of, in order. First, which asymptotic regime a claimed theorem is in: \(\ell \to \infty\) with \(G\) fixed is Fan and Lin and settles nothing here. Second, whether the parity-check matrix is systematic, without which the statement is false. Third, whether the result is asymptotic or a concrete bound that degenerates as \(|G|\) grows, which is exactly how the 2026 progress falls short.