Generalizing the Augot-Finiasz PKE to Other Code Classes

Anmoal Porwal, Anna Baumeister, Violetta Weger, Antonia Wachter-Zeh, Pierre Loidreau

This paper, presented by a team from the Technical University of Munich and the University of Rennes, provides a rigorous post-mortem and generalization of a promising but embattled family of post-quantum cryptosystems.

TL;DR

The authors formalize a generalized framework for the Augot-Finiasz public-key encryption (PKE) scheme, which offers significantly smaller keys than the classic McEliece system by keeping the underlying code public. However, they demonstrate that most structured code classes—including Reed-Solomon, Gabidulin, BCH, and LRPC codes—are inherently insecure in this framework due to powerful linearization and algebraic attacks.

What Problem Does This Paper Address?

In the race to standardize post-quantum cryptography, the McEliece system is a frontrunner. While highly secure, it suffers from massive public key sizes because it must "hide" the structure of its underlying error-correcting code.

The Augot-Finiasz (AF) system, introduced in 2003, proposed a radical alternative: what if the code is public, and the secret is hidden in the error instead? This approach allows for much smaller keys. Unfortunately, the original AF (based on Reed-Solomon codes) and its rank-metric successors (based on Gabidulin codes) were systematically broken. This paper asks a fundamental question: Is the AF framework fundamentally flawed, or can it be saved by using a different class of error-correcting codes?

Methods

The authors approach this by creating a unified mathematical framework that generalizes all previous AF-like proposals.

  1. Formalization: They define the PKE in terms of a public generator matrix $G$. The public key is a "noisy" codeword, and the ciphertext is another noisy codeword randomized by a secret scalar $\alpha$.
  2. Reductions: They reduce the system's correctness to the existence of an efficient "error-erasure decoder" for the chosen code class. They reduce its security to a new hardness assumption they call the Supercode Decoding Problem.
  3. Unified Attack Analysis: They use this framework to explain why previous "repairs" like RAMESSES and LIGA failed. They show that for highly structured codes, an attacker can set up a system of linearized equations to solve for the secret randomization factor $\alpha$ and the message simultaneously.

Datasets

Not discussed in the paper. As a theoretical work in cryptography, the "evaluation" consists of mathematical proofs and complexity analyses rather than empirical testing on standard datasets.

Key Insights and Ideas

  • The "Supercode" Perspective: The authors show that an attacker isn't just decoding the original code; they are decoding a "supercode" formed by the union of the public code and the public key. If this supercode is easy to decode, the system is broken.
  • The Incompatibility Triangle: For Reed-Solomon and Gabidulin codes, the authors prove a "no-go" theorem. They show that the parameters required for (1) successful decryption, (2) resisting linearization attacks, and (3) resisting interleaved decoding attacks are mathematically incompatible. You can pick any two, but never all three.
  • Structure is a Liability: The very algebraic properties that make codes like BCH or Reed-Solomon efficient to decode are exactly what attackers use to build linearization equations. The paper suggests that "structured" codes are likely all insecure for this specific framework.

Key Results

  • Negative Results for RS/Gabidulin: The paper provides a definitive proof that these codes cannot be used securely in the AF framework, even with interleaving or "shorter message" variations.
  • BCH Vulnerability: They demonstrate that any code class where decoding involves solving a linear system of syndrome coefficients (like BCH codes) is likely insecure.
  • LRPC Breakdown: They show that Low-Rank Parity Check (LRPC) codes are insecure because an attacker can recover the error support by intersecting subspaces—a technique specific to the rank metric.
  • Security Reduction: The formalization of the "Supercode Decoding Problem" provides a clear target for future cryptanalysis of any new AF-like proposals.

Limitations and Future Work

The paper is primarily a "negative" result—it tells us what doesn't work. The authors acknowledge that they have not yet found a code class that is both efficiently decodable (for the user) and hard to decode in the "supercode" sense (for the attacker).

Future Directions: * Combinatorial Codes: The authors suggest looking into codes with less algebraic structure and more "combinatorial" properties, which might resist linearization. * Alternative Randomization: Instead of simple scalar multiplication by $\alpha$, future research could explore more complex ways to randomize the public key during encryption that don't lend themselves to linear systems of equations.

Summary updated

BibTeX
@inproceedings{porwal2024generalizing,
  author = {Anmoal Porwal and Anna Baumeister and Violetta Weger and Antonia Wachter-Zeh and Pierre Loidreau},
  title = {{Generalizing the Augot-Finiasz PKE to Other Code Classes}},
  booktitle = {CBCrypto},
  year = {2024},
  doi = {10.1007/978-3-031-90229-1\_2},
}

Loading related content...

Figure