LIGA: A Cryptosystem Based on the Hardness of Rank-Metric List and\n Interleaved Decoding

Julian Renner, Sven Puchinger, Antonia Wachter-Zeh

TL;DR

LIGA is a post-quantum cryptosystem that fixes the broken Faure–Loidreau (FL) system by redesigning its key generation. By proving that previous structural attacks were actually hidden "interleaved decoding" problems, the authors created a system that is secure against polynomial-time attacks while maintaining tiny key and ciphertext sizes.

What Problem Does This Paper Address?

As we prepare for the era of quantum computing, traditional encryption like RSA and Elliptic Curve Cryptography (ECC) will become obsolete. Code-based cryptography is a leading "post-quantum" alternative, but it often suffers from massive public keys (sometimes hundreds of kilobytes).

Rank-metric systems, specifically those using Gabidulin codes, offer a solution with much smaller keys. However, a promising system called Faure–Loidreau (FL) was recently "broken" by a structural attack known as the GOT attack. The authors of this paper set out to understand why FL was broken and how to build a successor—LIGA—that retains FL's efficiency but blocks the attack.

Methods

The researchers' primary breakthrough was a new coding-theoretic interpretation of the GOT attack. They proved that the attack is mathematically equivalent to decoding an interleaved Gabidulin code.

Standard Gabidulin decoders work up to a certain error radius. Interleaved decoders can often go beyond that limit, which is exactly what the GOT attack was doing to recover the secret key. To fix this, LIGA introduces a modified Key Generation algorithm:

  • Controlled Failure: Instead of choosing random errors for the public key, LIGA specifically constructs errors from a subspace (parameterized by a value $\zeta$) such that the resulting "interleaved" problem falls into a known "failure zone" for all polynomial-time decoders.
  • Error-Erasure Interpretation: The authors re-interpreted the decryption process as a form of error-erasure decoding, which allows for highly efficient, constant-time implementations.
  • KEM/DEM Transformation: They provide a version of LIGA that works as a Key Encapsulation Mechanism (KEM), achieving IND-CCA2 security (the "gold standard" for modern encryption) in the random oracle model.

Datasets

As a theoretical cryptography paper, it does not use training datasets. Instead, it evaluates performance using specific parameter sets designed for 128, 192, and 256-bit security levels. These are compared against NIST Post-Quantum Cryptography competition proposals, including:

  • RQC and ROLLO (Rank-metric peers)
  • BIKE (MDPC-based)
  • Classic McEliece (The "gold standard" of code-based crypto)

Key Insights and Ideas

  • The "Aha" Moment: Structural attacks on these codes aren't just arbitrary algebraic tricks; they are specific instances of decoding interleaved codes. If you can ensure the interleaved decoder fails, the attack fails.
  • Zero Decryption Failure Rate (DFR): Many modern PQC schemes (like Kyber or BIKE) have a tiny chance that a valid ciphertext won't decrypt correctly. LIGA guarantees correct decryption every time, simplifying system integration.
  • Resistance to Timing Attacks: Because Gabidulin codes can be encoded and decoded using constant-time algorithms, LIGA is naturally resistant to side-channel attacks that try to steal keys by measuring how long a computer takes to decrypt a message.
  • Small Footprint: LIGA achieves a sweet spot in efficiency, offering ciphertexts around 1 KB for 128-bit security—orders of magnitude smaller than systems like Classic McEliece.

Key Results

The paper demonstrates that LIGA is a highly competitive post-quantum candidate:

  • Security: It is proven IND-CPA secure in the standard model and IND-CCA2 secure as a KEM.
  • Efficiency: For 128-bit security (LIGA-128), the public key is only 6.3 KB and the ciphertext is 1 KB.
  • Comparison: Compared to the NIST proposal ROLLO-I-128, LIGA has a slightly larger public key but avoids the decryption failures that plague ROLLO. Compared to Classic McEliece, LIGA's public key is roughly 40x smaller.

Limitations and Future Work

  • New Hardness Assumptions: LIGA relies on the hardness of decoding interleaved Gabidulin codes in the "failure" regime. While the authors provide extensive exponential-time attack analysis, these specific problems are newer and less "battle-tested" than the problems underlying RSA.
  • Algebraic Attack Evolution: The most potent threats to LIGA are currently algebraic attacks (using Gröbner bases). As these algorithms improve, LIGA's parameters may need to be scaled up.
  • Weak Key Probability: There is a theoretical (though mathematically negligible) chance of generating a "weak key." The authors provide bounds to ensure this probability is lower than $2^{-128}$, but rigorous auditing of key generation implementations is required.

Summary updated

Abstract

We propose the new rank-metric code-based cryptosystem LIGA which is based on\nthe hardness of list decoding and interleaved decoding of Gabidulin codes. LIGA\nis an improved variant of the Faure-Loidreau (FL) system, which was broken in a\nstructural attack by Gaborit, Otmani, and Tal\\'e Kalachi (GOT, 2018). We keep\nthe FL encryption and decryption algorithms, but modify the insecure key\ngeneration algorithm. Our crucial observation is that the GOT attack is\nequivalent to decoding an interleaved Gabidulin code. The new key generation\nalgorithm constructs public keys for which all polynomial-time interleaved\ndecoders fail---hence LIGA resists the GOT attack. We also prove that the\npublic-key encryption version of LIGA is IND-CPA secure in the standard model\nand the KEM version is IND-CCA2 secure in the random oracle model, both under\nhardness assumptions of formally defined problems related to list decoding and\ninterleaved decoding of Gabidulin codes. We propose and analyze various\nexponential-time attacks on these problems, calculate their work factors, and\ncompare the resulting parameters to NIST proposals. The strengths of LIGA are\nshort ciphertext sizes and (relatively) small key sizes. Further, LIGA\nguarantees correct decryption and has no decryption failure rate. It is not\nbased on hiding the structure of a code. Since there are efficient and\nconstant-time algorithms for encoding and decoding Gabidulin codes, timing\nattacks on the encryption and decryption algorithms can be easily prevented.\n
BibTeX
@article{renner2018liga,
  author = {Julian Renner and Sven Puchinger and Antonia Wachter-Zeh},
  title = {{LIGA: A Cryptosystem Based on the Hardness of Rank-Metric List and\textbackslash\{\}n Interleaved Decoding}},
  journal = {IACR Cryptol. ePrint Arch.},
  year = {2018},
  url = {https://openreview.net/forum?id=2t7S5jtoZ08},
}
Figure