Folding Alternant and Goppa Codes With Non-Trivial Automorphism Groups

Jean-Charles Faugère, Ayoub Otmani, Ludovic Perret, Frédéric de Portzamparc, Jean-Pierre TillichIEEE Trans. Information Theory 2016 · DOI

TL;DR

This paper introduces a "folding" technique that exploits symmetries in alternant and Goppa codes, commonly used in compact McEliece cryptosystems. The authors demonstrate that this folding process can reduce the complexity of key-recovery attacks on these cryptosystems, effectively undermining the security benefits of using symmetric codes for key size reduction.

What Problem Does This Paper Address?

The McEliece cryptosystem, a prominent code-based public-key encryption scheme, suffers from large key sizes, which limits its practical applications. A common approach to mitigate this is to use specific subclasses of alternant and Goppa codes that possess non-trivial automorphism groups. These symmetries allow for more compact representations of the public key (e.g., using quasi-cyclic or quasi-dyadic codes). The hope was that these symmetric codes would maintain their security despite the reduced key size. However, recent attacks have shown that these symmetric structures can introduce vulnerabilities. This paper addresses the fundamental question of whether these symmetric codes, designed for key compression, inherently weaken the cryptosystem's security against key-recovery attacks.

Methods

The core contribution of this paper is the introduction of a "folding" operation. This operation takes a code with a non-trivial automorphism group and produces a new, smaller code by summing up codeword coordinates that belong to the same orbit under the group's action. The key insight is that folding the dual of an alternant or Goppa code with an affine-induced automorphism group results in the dual of a smaller alternant or Goppa code, respectively. This preserves the code structure while significantly reducing its parameters. The authors unify various constructions of symmetric alternant and Goppa codes (QC, QD, QM) under a common principle: their supports are globally invariant under affine transformations. This unified view allows for a generalized construction and analysis of these codes.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Folding as a Weakness: The "folding" technique, while seemingly a mathematical curiosity, directly exposes a fundamental weakness in symmetric alternant/Goppa codes used for key compression. It shows that the compact representation is an "inflated" version of a smaller, non-symmetric code.
  • Unified Construction Principle: The paper reveals that many existing constructions of symmetric alternant and Goppa codes (QC, QD, QM) share a common underlying principle: their supports are invariant under affine transformations. This provides a unified framework for understanding and generalizing these codes.
  • Preservation of Code Structure: A crucial finding is that folding the dual of an alternant/Goppa code with an affine-induced automorphism group results in the dual of a smaller alternant/Goppa code. This structural preservation is key to the attack's effectiveness.
  • Direct Link to Key Recovery: The folding operation directly relates the key-recovery problem on the original symmetric code to the problem on a smaller, non-symmetric code. This significantly reduces the complexity of algebraic attacks.

Key Results

The paper demonstrates that using symmetric alternant/Goppa codes in McEliece-like schemes introduces a fundamental weakness. The folding operation allows for a reduction in the code's length and dimension by the size of the orbits under the automorphism group. This directly translates to a reduction in the complexity of key-recovery attacks. For instance, the authors show that a key-recovery attack on a QD Goppa code of length 8192 and dimension 4096 can be reduced to the problem of recovering the key for a Goppa code of length 64 and dimension 32. This implies that the security of compact McEliece schemes is not better than that of a reduced, non-symmetric scheme.

Limitations and Future Work

  • Affine-Induced Automorphisms: The folding technique and its security implications are primarily demonstrated for codes with affine-induced automorphism groups. The paper acknowledges that symmetric codes can also arise from the action of the projective semi-linear group (which includes more general affine transformations) and poses it as an open question whether folding these codes also preserves the alternant/Goppa structure.
  • General Automorphism Groups: The paper focuses on cyclic groups and groups isomorphic to (Z/pZ)^. The general case of arbitrary non-cyclic automorphism groups is considered beyond the scope of this work.
  • Practical Parameter Choices: While the paper shows that compact schemes are inherently weaker, it suggests that careful parameter selection might still allow for a good reduction in key size while keeping key-recovery attacks computationally expensive. However, this requires careful analysis due to recent advances in cryptanalysis.
  • Future Research: The authors suggest further research into the folding of codes with more general automorphism groups and the careful selection of parameters for compact McEliece schemes to balance key size reduction and security.

Summary updated

BibTeX
@article{faugere2016folding,
  author = {Jean-Charles Faugère and Ayoub Otmani and Ludovic Perret and Frédéric de Portzamparc and Jean-Pierre Tillich},
  title = {{Folding Alternant and Goppa Codes With Non-Trivial Automorphism Groups}},
  journal = {IEEE Trans. Information Theory},
  year = {2016},
  doi = {10.1109/tit.2015.2493539},
}
Figure