LIGA: a cryptosystem based on the hardness of rank-metric list and interleaved decoding
From MaRDI portal
Publication:2034992
DOI10.1007/S10623-021-00861-ZzbMATH Open1468.94414arXiv1812.04892OpenAlexW3153839025MaRDI QIDQ2034992FDOQ2034992
Authors: Julian Renner, Sven Puchinger, Antonia Wachter-Zeh 
Publication date: 23 June 2021
Published in: Designs, Codes and Cryptography (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1812.04892
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
- Title not available (Why is that?)
- Bilinear forms over a finite field, with applications to coding theory
- Theory of codes with maximum rank distance
- Coding for Errors and Erasures in Random Network Coding
- A Rank-Metric Approach to Error Control in Random Network Coding
- Error-Correcting Codes in Projective Space
- Bounds on List Decoding of Rank-Metric Codes
- Secure integration of asymmetric and symmetric encryption schemes
- Grover vs. McEliece
- Error and erasure correcting algorithms for rank codes
- List and unique error-erasure decoding of interleaved Gabidulin codes with interpolation techniques
- Skew-Feedback Shift-Register Synthesis and Decoding Interleaved Gabidulin Codes
- Semantic security for the McEliece cryptosystem without random oracles
- Fast operations on linearized polynomials and their applications in coding theory
- On the genericity of maximum rank distance and Gabidulin codes
- Progress in Cryptology – Mycrypt 2005
- A new rank metric codes based encryption scheme
- A modular analysis of the Fujisaki-Okamoto transformation
- Fast Multiplication for Skew Polynomials
- Reducible rank codes and their applications to cryptography
- Some Gabidulin Codes Cannot Be List Decoded Efficiently at any Radius
- Polynomial-time key recovery attack on the Faure-Loidreau scheme based on Gabidulin codes
- Title not available (Why is that?)
- Coding and Cryptography
- An IND-CCA-secure code-based encryption scheme using rank metric
- Partition-balanced families of codes and asymptotic enumeration in coding theory
- Preventing timing attacks against RQC using constant time decoding of Gabidulin codes
- On the List Decodability of Rank Metric Codes
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
- On decoding high-order interleaved sum-rank-metric codes
- Extending Coggia-Couvreur attack on Loidreau's rank-metric cryptosystem
- Cryptanalysis and repair of a Gabidulin code based cryptosystem from ACISP 2018
- Rank-metric codes and their applications
Uses Software
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)
