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

DOI10.1007/S10623-017-0402-0zbMATH Open1420.94064arXiv1606.07760OpenAlexW2963026014WikidataQ62039147 ScholiaQ62039147MaRDI QIDQ1647553FDOQ1647553

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

Publication date: 26 June 2018

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

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.

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

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

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)

Cites Work

• Structural attacks for public key cryptosystems based on Gabidulin codes
• Distinguisher-based attacks on public-key cryptosystems using Reed-Solomon codes
• Title not available (Why is that?)
• Theory of codes with maximum rank distance
• Isometries for rank distance and permutation group of gabidulin codes
• On the Complexity of the Rank Syndrome Decoding Problem
• Polynomial Time Attack on Wild McEliece over Quadratic Extensions
• Progress in Cryptology – Mycrypt 2005
• Attacks and counter-attacks on the GPT public key cryptosystem
• Severely denting the Gabidulin version of the McEliece public key cryptosystem
• The Security of the Gabidulin Public Key Cryptosystem
• Reducible rank codes and their applications to cryptography
• Coding and Cryptography
• Improved cryptanalysis of rank metric schemes based on Gabidulin codes
• Modified GPT PKC with right scrambler
• Square Code Attack on a Modified Sidelnikov Cryptosystem
• Designing a Rank Metric Based McEliece Cryptosystem
• Title not available (Why is that?)
• Cryptanalyzing the Polynomial-Reconstruction Based Public-Key System Under Optimal Parameter Choice
• Coding and Cryptography
• Public Key Cryptography – PKC 2004

Cited In (10)

• Decoding supercodes of Gabidulin codes and applications to cryptanalysis
• 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
• A new McEliece-type cryptosystem using Gabidulin-Kronecker product codes
• Structural attacks for public key cryptosystems based on Gabidulin codes
• Cryptanalysis and repair of a Gabidulin code based cryptosystem from ACISP 2018
• Randomized Decoding of Gabidulin Codes Beyond the Unique Decoding Radius

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)