Polynomial-time key recovery attack on the Faure-Loidreau scheme based on Gabidulin codes

DOI10.1007/S10623-017-0402-0MaRDI QIDQ1647553zbMATH OpenOpenAlexWikidataFDO

Authors Philippe Gaborit, Ayoub Otmani, Hervé Talé Kalachi

Publication date 26 June 2018

Published in Designs, Codes and Cryptography (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1606.07760

zbMATH Keywords

Gabidulin codepost-quantum cryptographyGPT encryption scheme

Mathematics Subject Classification ID

Cryptography (94A60) Algebraic coding theory; cryptography (number-theoretic aspects) (11T71) Quantum cryptography (quantum-theoretic aspects) (81P94)

Abstract: Encryption schemes based on the rank metric lead to small public key sizes of order of few thousands bytes which represents a very attractive feature compared to Hamming metric-based encryption schemes where public key sizes are of order of hundreds of thousands bytes even with additional structures like the cyclicity. The main tool for building public key encryption schemes in rank metric is the McEliece encryption setting used with the family of Gabidulin codes. Since the original scheme proposed in 1991 by Gabidulin, Paramonov and Tretjakov, many systems have been proposed based on different masking techniques for Gabidulin codes. Nevertheless, over the years all these systems were attacked essentially by the use of an attack proposed by Overbeck. In 2005 Faure and Loidreau designed a rank-metric encryption scheme which was not in the McEliece setting. The scheme is very efficient, with small public keys of size a few kiloBytes and with security closely related to the linearized polynomial reconstruction problem which corresponds to the decoding problem of Gabidulin codes. The structure of the scheme differs considerably from the classical McEliece setting and until our work, the scheme had never been attacked. We show in this article that this scheme like other schemes based on Gabidulin codes, is also vulnerable to a polynomial-time attack that recovers the private key by applying Overbeck's attack on an appropriate public code. As an example we break concrete proposed $80$ bits security parameters in a few seconds.

Recommendations

• A new rank metric codes based encryption scheme
• A new encryption scheme based on rank metric codes
• Improved cryptanalysis of rank metric schemes based on Gabidulin codes
• Extending Coggia-Couvreur attack on Loidreau's rank-metric cryptosystem
• A new Gabidulin-like code and its application in cryptography

Cites work

• scientific article; zbMATH DE number 177612 (Why is no real title available?)
• scientific article; zbMATH DE number 2009958 (Why is no real title available?)
• Attacks and counter-attacks on the GPT public key cryptosystem
• Coding and Cryptography
• Coding and Cryptography
• Cryptanalyzing the Polynomial-Reconstruction Based Public-Key System Under Optimal Parameter Choice
• Designing a Rank Metric Based McEliece Cryptosystem
• Distinguisher-based attacks on public-key cryptosystems using Reed-Solomon codes
• Improved cryptanalysis of rank metric schemes based on Gabidulin codes
• Isometries for rank distance and permutation group of gabidulin codes
• Modified GPT PKC with right scrambler
• On the Complexity of the Rank Syndrome Decoding Problem
• Polynomial time attack on wild McEliece over quadratic extensions
• Progress in Cryptology – Mycrypt 2005
• Public Key Cryptography – PKC 2004
• Reducible rank codes and their applications to cryptography
• Severely denting the Gabidulin version of the McEliece public key cryptosystem
• Square code attack on a modified Sidelnikov cryptosystem
• Structural attacks for public key cryptosystems based on Gabidulin codes
• The security of the Gabidulin public key cryptosystem
• Theory of codes with maximum rank distance

Cited in

(14)

• On the security of the modified dual-Ouroboros PKE using Gabidulin codes
• Decoding supercodes of Gabidulin codes and applications to cryptanalysis
• A new rank metric codes based encryption scheme
• Randomized decoding of Gabidulin codes beyond the unique decoding radius
• Two modifications for Loidreau's code-based cryptosystem
• Extending Coggia-Couvreur attack on Loidreau's rank-metric cryptosystem
• LIGA: a cryptosystem based on the hardness of rank-metric list and interleaved decoding
• Injective rank metric trapdoor functions with homogeneous errors
• Partition-balanced families of codes and asymptotic enumeration in coding theory
• Structural attacks for public key cryptosystems based on Gabidulin codes
• A new McEliece-type cryptosystem using Gabidulin-Kronecker product codes
• Cryptanalysis and repair of a Gabidulin code based cryptosystem from ACISP 2018
• Cryptanalysis of Rank-Metric Schemes Based on Distorted Gabidulin Codes
• Weak keys in the Faure-Loidreau cryptosystem

Describes a project that uses

Uses Software

• McEliece

This page was built for publication: Polynomial-time key recovery attack on the Faure-Loidreau scheme based on Gabidulin codes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1647553)