On a Rank-Metric Code-Based Cryptosystem with Small Key Size

Julian Renner, Sven Puchinger, Antonia Wachter-Zeh

Abstract: We propose the new rank-metric code-based cryptosystem LIGA which is based on the hardness of list decoding and interleaved decoding of Gabidulin codes. LIGA is an improved variant of the Faure-Loidreau (FL) system, which was broken in a structural attack by Gaborit, Otmani, and Tal'e Kalachi (GOT, 2018). We keep the FL encryption and decryption algorithms, but modify the insecure key generation algorithm. Our crucial observation is that the GOT attack is equivalent to decoding an interleaved Gabidulin code. The new key generation algorithm constructs public keys for which all polynomial-time interleaved decoders fail---hence LIGA resists the GOT attack. We also prove that the public-key encryption version of LIGA is IND-CPA secure in the standard model and the KEM version is IND-CCA2 secure in the random oracle model. The strengths of LIGA are short ciphertext sizes and (relatively) small key sizes, with no decryption failure rate.

Introduction

As the era of quantum computing approaches, traditional public-key cryptography—relying on the hardness of factoring or discrete logarithms—faces an existential threat. Code-based cryptography has emerged as a leading post-quantum candidate due to its long-standing security history. However, traditional schemes like McEliece suffer from a significant practical hurdle: massive public key sizes, often reaching hundreds of kilobytes.

The Faure–Loidreau (FL) system was originally proposed to address this by utilizing rank-metric codes, specifically Gabidulin codes. By representing the public key as a compact vector rather than a large matrix, FL promised a much smaller footprint. However, the structural "GOT" attack in 2018 appeared to render the system insecure. This paper presents LIGA, a "repaired" version of the FL system that maintains its efficiency while systematically neutralizing the GOT attack.

The Faure-Loidreau System and the GOT Attack

The original FL system relies on the properties of Gabidulin codes over extension fields. The security of the system was predicated on the difficulty of recovering the private structure of the code from the public key.

Table 1: Parameters and restrictions for the FL system.

In the original key generation process (Algorithm 1), the public key is constructed using a generator vector and a specific error vector. The GOT attack demonstrated that an attacker could exploit the structure of this public key to recover the secret key in polynomial time.

Algorithm 1: The original Faure-Loidreau key generation process.

Methods: A Coding-Theoretic Repair

The authors' primary contribution is a new coding-theoretic interpretation of the FL system. They provide two critical insights:

  1. Decryption as Error-Erasure Decoding: The legitimate receiver's decryption process is mathematically equivalent to decoding a Gabidulin code where a portion of the error (the "erasure") is known to the holder of the private key.
  2. Public Key as Interleaved Code: Crucially, the authors prove that the structural GOT attack is mathematically identical to the problem of decoding an interleaved Gabidulin code. The public key itself can be viewed as a corrupted codeword of such a code.

The "Intentional Failure" Strategy

To fix the system, the authors propose a modified key generation algorithm. Since the GOT attack succeeds only if a specific interleaved Gabidulin decoder can successfully recover the private key, the authors intentionally construct the "error" part of the public key ($z$) such that its components are linearly dependent. This dependency is engineered to guarantee that all known efficient interleaved decoders will fail to recover the secret key. This creates a security barrier that resists the most potent known attack while still allowing the legitimate user—who possesses additional private information—to decrypt messages without failure.

Results: Efficiency and Security

The repaired FL system, LIGA, offers a dramatic reduction in key size compared to the classic McEliece system while maintaining robust security properties. It is proven to be IND-CPA secure for public-key encryption and IND-CCA2 secure for Key Encapsulation Mechanisms (KEM).

Security Level LIGA Public Key Size McEliece Public Key Size
80/90-bit 1.86 KB ~79 KB
128-bit 1.92 KB 242 KB
256-bit 4.31 KB >1.1 MB

Beyond key size, LIGA offers several advantages over other modern alternatives like MDPC or LRPC schemes. Most notably, LIGA guarantees correct decryption and has zero decryption failure rate, which eliminates a common side-channel attack vector. Furthermore, because it is not based on hiding the structure of a code, and because Gabidulin codes have efficient constant-time encoding/decoding algorithms, it is naturally resistant to certain timing attacks.

Conclusion

By bridging the gap between cryptanalysis and interleaved decoding theory, LIGA successfully rehabilitates the Faure-Loidreau framework. It provides a highly efficient, post-quantum secure alternative with some of the smallest public key sizes available in code-based cryptography today. Future work will focus on developing production-ready, constant-time implementations to further validate its practical utility in real-world secure communications.

Summary updated

Abstract

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