LIGA: a cryptosystem based on the hardness of rank-metric list and interleaved decoding
From MaRDI portal
Publication:2034992
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.
Recommendations
- On the security of a Loidreau rank metric code based encryption scheme
- LARA: a design concept for lattice-based encryption
- Extending Coggia-Couvreur attack on Loidreau's rank-metric cryptosystem
- An algebraic attack on rank metric code-based cryptosystems
- The rank-based cryptography library
- A new encryption scheme based on rank metric codes
- scientific article; zbMATH DE number 1759341
- New technique for decoding codes in the rank metric and its cryptography applications
- LizarMong: excellent key encapsulation mechanism based on RLWE and RLWR
- SETLA: Signature and Encryption from Lattices
Cites work
- scientific article; zbMATH DE number 2009958 (Why is no real title available?)
- scientific article; zbMATH DE number 967590 (Why is no real title available?)
- A Rank-Metric Approach to Error Control in Random Network Coding
- A modular analysis of the Fujisaki-Okamoto transformation
- A new rank metric codes based encryption scheme
- An IND-CCA-secure code-based encryption scheme using rank metric
- Bilinear forms over a finite field, with applications to coding theory
- Bounds on List Decoding of Rank-Metric Codes
- Coding and Cryptography
- Coding for Errors and Erasures in Random Network Coding
- Error and erasure correcting algorithms for rank codes
- Error-Correcting Codes in Projective Space
- Fast Multiplication for Skew Polynomials
- Fast operations on linearized polynomials and their applications in coding theory
- Grover vs. McEliece
- List and unique error-erasure decoding of interleaved Gabidulin codes with interpolation techniques
- On the List Decodability of Rank Metric Codes
- On the genericity of maximum rank distance and Gabidulin codes
- Partition-balanced families of codes and asymptotic enumeration in coding theory
- Polynomial-time key recovery attack on the Faure-Loidreau scheme based on Gabidulin codes
- Preventing timing attacks against RQC using constant time decoding of Gabidulin codes
- Progress in Cryptology – Mycrypt 2005
- Reducible rank codes and their applications to cryptography
- Secure integration of asymmetric and symmetric encryption schemes
- Semantic security for the McEliece cryptosystem without random oracles
- Skew-Feedback Shift-Register Synthesis and Decoding Interleaved Gabidulin Codes
- Some Gabidulin Codes Cannot Be List Decoded Efficiently at any Radius
- Theory of codes with maximum rank distance
Cited in
(7)- Decoding supercodes of Gabidulin codes and applications to cryptanalysis
- On the list decodability of rank-metric codes containing Gabidulin codes
- Two modifications for Loidreau's code-based cryptosystem
- Extending Coggia-Couvreur attack on Loidreau's rank-metric cryptosystem
- On decoding high-order interleaved sum-rank-metric codes
- Cryptanalysis and repair of a Gabidulin code based cryptosystem from ACISP 2018
- Rank-metric codes and their applications
This page was built for publication: LIGA: a cryptosystem based on the hardness of rank-metric list and interleaved decoding
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2034992)
