% =====================================================================
%  CONJURA CONJECTURE STATEMENT
%  Bombar-Couteau-Couvreur-Ducros conjecture that the Gaborit-Zemor
%  minimum-distance result extends from cyclic groups to arbitrary
%  abelian groups, in the regime where the group grows.
%  Requires conjura-conjecture.cls in the same directory.
% =====================================================================
\documentclass{conjura-conjecture}

\runninghead{QUASI-ABELIAN CODES AS THE GROUP GROWS}

\newcommand{\Fq}{\mathbb{F}_{q}}
\newcommand{\FqG}{\mathbb{F}_{q}[G]}
\newcommand{\dmin}{d_{\min}}
\newcommand{\hq}{h_{q}}

\begin{document}

\cjkicker{CONJURA \textperiodcentered{} OPEN PROBLEM}
\cjtitle{Quasi-Abelian Codes Meet the Gilbert-Varshamov Bound as the
  Group Grows}
\cjsubtitle{Known for cyclic groups, and for arbitrary abelian groups in
  the other asymptotic regime; the case the security of QA-SD actually
  needs is neither}
\cjstatus{Statement: AI-written from Maxime Bombar, Geoffroy Couteau,
  Alain Couvreur and Cl\'ement Ducros, \emph{Correlated Pseudorandomness
  from the Hardness of Quasi-Abelian Decoding}, IACR ePrint 2023/845,
  CRYPTO 2023. Not yet checked by a human. The source names the direction
  and says the development is out of reach of the article, leaving it as
  a conjecture; it does not print a formal statement, so the
  formalisation below is this statement's reading and is flagged as such.
  Partially settled since: concrete non-asymptotic bounds are now known
  for particular groups, and the general asymptotic question is restated
  as open in that follow-up.}
\cjcategory{\emph{Coding theory; code-based assumptions}.}

\vspace{0.4em}

\begin{informalconjecture}
Modern 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 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, which is the regime the cryptographic
parameters actually live in, and it is a theorem only when the group is
cyclic, due to Gaborit and Z\'emor. The conjecture is that the cyclic
restriction can be dropped.
\end{informalconjecture}

\section{The setting}\label{sec:setting}

Let $G$ be a finite abelian group and $\FqG$ its group algebra, the
$\Fq$-vector space with basis $G$ and multiplication induced by the group
law. An $\FqG$-submodule of $(\FqG)^{\ell}$ is a \emph{quasi-$G$ code of
index $\ell$}; for $G$ cyclic these are the quasi-cyclic codes, and for
$G$ trivial they are all linear codes. A quasi-$G$ code of rank $k$ is
the row space of a matrix $\Gamma \in (\FqG)^{k \times \ell}$, and
$\Gamma$ is \emph{systematic} if $\Gamma = (I_k \mid \Gamma')$. As a
code over $\Fq$ its length is $\ell \cdot |G|$ and its rate is
$r = k/\ell$.

The \emph{quasi-abelian syndrome decoding} problem $\mathrm{QA\text{-}SD}$
is syndrome decoding for such codes, with the parity-check matrix in
systematic form. It generalises both plain and quasi-cyclic syndrome
decoding, the latter being the assumption behind the NIST round-4
submissions BIKE and HQC\@.

\begin{theorem}[Security against linear tests reduces to distance, {\cite[\S 4.5]{BCCD23}}]\label{thm:lineartest}
If the parity-check matrix $H$ of a quasi-$G$ code has the property that
the code generated by $H$ has large minimum distance with high
probability over the choice of $H$, then $\mathrm{QA\text{-}SD}$ resists
every attack in the linear test framework.
\end{theorem}

So everything turns on the minimum distance of a random quasi-$G$ code,
and there are two ways to send it to infinity.

\begin{theorem}[Fixed group, growing index, {\cite[Thm.~2.1]{FL15}}]\label{thm:fanlin}
Let $G$ be a finite abelian group and $(C_{\ell})_{\ell}$ a sequence of
random quasi-$G$ codes of index $\ell$ and rate $r \in (0,1)$. For
$\delta \in (0, 1 - 1/q)$,
\[
  \lim_{\ell \to \infty}
  \Pr\!\left[ \frac{\dmin(C_{\ell})}{|G|} > \delta \ell \right]
  = \begin{cases} 1 & \text{if } r < 1 - \hq(\delta),\\
                  0 & \text{if } r > 1 - \hq(\delta),\end{cases}
\]
both limits converging exponentially fast, over the uniform choice of a
generator matrix $\Gamma_{\ell} \in (\FqG)^{k \times \ell}$.
\end{theorem}

Fan and Lin's result is asymptotic in $\ell$ with $G$ fixed, and the
source records why that is the wrong way round for its purpose: ``the
exponent depends on $|G|$: the larger the group $G$, the higher this
probability''. Cryptographic parameters have $k$ and $\ell$ small ---
often $k=1$, $\ell$ a small constant --- and $|G|$ large.

In that regime the corresponding 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\'emor showed various families of
random double-circulant codes asymptotically satisfy a logarithmic
improvement on it.

\section{Notation and parameters}\label{sec:notation}

\begin{itemize}[nosep]
  \item $G$ is a finite abelian group, $|G| \to \infty$ along the family;
    $q$ is the field size, fixed.
  \item $k$ is the rank and $\ell$ the index of the code, both constant;
    $r = k/\ell$ is the rate. The code has length $\ell \cdot |G|$ over
    $\Fq$.
  \item $\hq$ is the $q$-ary entropy function, and
    $r < 1 - \hq(\delta)$ is the Gilbert-Varshamov condition.
  \item \emph{Systematic} means the parity-check matrix is
    $(I_k \mid \cdot)$ over $\FqG$; this is not cosmetic, see
    Remark~\ref{rem:bias}.
\end{itemize}

\section{The conjecture}\label{sec:conjectures}

\begin{conjecture}[{\cite[\S 1.2, \S 4.5]{BCCD23}}]\label{conj:main}
Theorem~\ref{thm:fanlin} holds in the other asymptotic regime, for every
abelian $G$ rather than only cyclic $G$. Concretely: fix $q$, constants
$k < \ell$ with $r = k/\ell$, and $\delta \in (0, 1-1/q)$ with
$r < 1 - \hq(\delta)$. Then for any family of finite abelian groups $G$
with $|G| \to \infty$, a random systematic quasi-$G$ code of rank $k$ and
index $\ell$ over $\Fq$ satisfies
$\dmin > \delta \cdot \ell \cdot |G|$ with probability tending to $1$.
\end{conjecture}

\begin{remark}[How the source states it, and what is being supplied
  here]\label{rem:framing}
The source states the direction twice and prints no formal statement.
Page 9: ``We conjecture an extension of Gaborit and Z\'emor 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.''

Conjecture~\ref{conj:main} is therefore this statement's formalisation of
a direction the source names, and two choices in it are ours rather than
the source's. It asks for the plain Gilbert-Varshamov threshold, not for
the \emph{logarithmic improvement} on it that Gaborit and Z\'emor
actually prove for double-circulant codes --- the weaker target, chosen
because it is what Theorem~\ref{thm:lineartest} needs and what the source
appeals to. And it fixes the systematic form, for the reason in
Remark~\ref{rem:bias}. A proof of the stronger statement with the
logarithmic improvement, or a proof for some restricted family of abelian
groups, is progress and should be reported as such.
\end{remark}

\begin{remark}[The caveat the source attaches, which is part of the
  statement]\label{rem:bias}
Without the systematic form the statement is false, and the source says
why. A syndrome $s = a_1 e_1 + a_2 e_2$ lies in the ideal
$(a_1, a_2) \subseteq \FqG$ generated by the blocks of the parity-check
matrix. Over a large field the blocks are invertible with overwhelming
probability and that ideal is everything; over a small field it need not
be, and then the syndrome distribution is biased --- ``when this ideal is
not the full ring, there is an obvious bias''.

In the growing-$|G|$ regime that is exactly the failure mode: ``in the
case of constant $k$, $\ell$ and growing $|G|$ there is a bias in the
QA-SD distribution when the ideal generated by the blocks in the input
parity-check matrix is not the full ring. This corresponds to the
parity-check matrix not being full-rank when seen as a matrix over
$\Fq[G]$. 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 the word \emph{heuristically}: this sentence is the source's reason
for believing the conjecture, not an argument for it.
\end{remark}

\begin{remark}[Progress since, and what it leaves open]\label{rem:progress}
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
$\Fq[(\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. They observe that their argument generalises to
$\Fq[(\mathbb{Z}/d\mathbb{Z})^{n}]$ for $d \mid q-1$ and to a generic
$\Fq[G]$ for a concrete group $G$.

That is real progress on Conjecture~\ref{conj:main} and does not settle
it, for a reason they state: their bound is non-asymptotic and becomes
vacuous as $|G| \to \infty$. ``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
conjecture explicitly as the source's: ``in [BCCD23] the authors
conjectured that Gaborit and Z\'emor'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 28 August 2026: concrete bounds for particular groups
over large fields, no asymptotic statement for growing $|G|$ beyond the
cyclic case.
\end{remark}

\begin{remark}[Why it is worth settling]\label{rem:why}
Conjecture~\ref{conj:main} is what makes the choice of group free. The
whole 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 the groups where a distance bound happens to be
available.

The source is also explicit that the hardness of the underlying decoding
problem is not in question in the same way: decoding a random
quasi-abelian code ``has 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 Encyclopedia of Coding Theory. What
is missing is the distance bound, not the belief.
\end{remark}

\section{Bibliography}

\begin{conjurabibliography}{99}

\bibitem[BCCD23]{BCCD23}
Maxime Bombar, Geoffroy Couteau, Alain Couvreur and Cl\'ement Ducros.
\emph{Correlated pseudorandomness from the hardness of quasi-abelian
decoding}.
IACR ePrint 2023/845; CRYPTO 2023.
The source. The conjecture is named on page 9 and again on page 20;
quasi-$G$ codes are defined in Section 4.1, the systematic-form caveat is
Remark 18, the linear-test reduction is Section 4.5, and the Fan-Lin
theorem is quoted there as Theorem 20.

\bibitem[FL15]{FL15}
Yun Fan and Liren Lin.
\emph{Thresholds of random quasi-abelian codes}.
IEEE Transactions on Information Theory, 61(1):82--90, 2015.
The theorem in the fixed-group, growing-index regime, including the
modular case; the statement the conjecture asks to transpose.

\bibitem[GZ06]{GZ06}
Philippe Gaborit and Gilles Z\'emor.
\emph{Asymptotic improvement of the Gilbert-Varshamov bound for linear
codes}.
Proc.\ IEEE International Symposium on Information Theory (ISIT) 2006,
pages 287--291, Seattle, June 2006.
The growing-group result for random double-circulant codes, with a
logarithmic improvement on the bound, whose extension to arbitrary
abelian groups is the conjecture.

\bibitem[Kas74]{Kas74}
T.\ Kasami.
\emph{A Gilbert-Varshamov bound for quasi-cyclic codes of rate 1/2}.
IEEE Transactions on Information Theory, 20(5):679, 1974.
The original Gilbert-Varshamov-like bound for quasi-cyclic codes that
Gaborit and Z\'emor improve.

\bibitem[Wil21]{Wil21}
Wolfgang Willems.
\emph{Codes in group algebras}, chapter 16.
Chapman and Hall/CRC, 2021.
The Encyclopedia of Coding Theory chapter in which decoding random
quasi-abelian codes is listed as an open research problem (Problem
16.10.5).

\bibitem[LLXYY26]{LLXYY26}
Zhe Li, Hongqing Liu, Chaoping Xing, Yizhou Yao and Chen Yuan.
\emph{More efficient SNARKs via quasi-abelian codes: faster, smaller, and
field-agnostic}.
IACR ePrint 2026/939.
The progress described in Remark~\ref{rem:progress}: concrete
non-asymptotic minimum-distance bounds over
$\Fq[(\mathbb{Z}/2\mathbb{Z})^{n}]$, and an explicit restatement of the
source's conjecture as still open.
[UNVERIFIED] --- this is a follow-up found by literature search on
28 August 2026, not a citation read off the source's own reference list;
the source predates it.

\bibitem[Pie67]{Pie67}
John N.\ Pierce.
\emph{Limit distribution of the minimum distance of random linear codes}.
IEEE Transactions on Information Theory, 13(1):595--599, 1967.
Cited by the source for the base case the conjecture generalises: random
linear codes meet the Gilbert-Varshamov bound.

\end{conjurabibliography}

\end{document}
