Repairing the Faure-Loidreau Public-Key Cryptosystem
Open Access
- 1 June 2018
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 21, 2426-2430
Abstract
A repair of the Faure-Loidreau (FL) public-key code-based cryptosystem is proposed. The FL cryptosystem is based on the hardness of list decoding Gabidulin codes which are special rank-metric codes. We prove that the recent structural attack on the system by Gaborit et al. is equivalent to decoding an interleaved Gabidulin code. Since all known polynomial-time decoders for these codes fail for a large constructive class of error patterns, we are able to construct public keys that resist the attack. It is also shown that all other known attacks fail for our repair and parameter choices. Compared to other code-based cryptosystems, we obtain significantly smaller key sizes for the same security level.Keywords
All Related Versions
This publication has 11 references indexed in Scilit:
- Some Gabidulin Codes Cannot Be List Decoded Efficiently at any RadiusIEEE Transactions on Information Theory, 2016
- On the Complexity of the Rank Syndrome Decoding ProblemIEEE Transactions on Information Theory, 2015
- List and unique error-erasure decoding of interleaved Gabidulin codes with interpolation techniquesDesigns, Codes and Cryptography, 2014
- Bounds on List Decoding of Rank-Metric CodesIEEE Transactions on Information Theory, 2013
- MDPC-McEliece: New McEliece variants from Moderate Density Parity-Check codes2013
- Skew-Feedback Shift-Register Synthesis and Decoding Interleaved Gabidulin CodesIEEE Transactions on Information Theory, 2011
- A New Public-Key Cryptosystem Based on the Problem of Reconstructing p–PolynomialsLecture Notes in Computer Science, 2006
- A New Structural Attack for GPT and Variants2005
- A Public Key Encryption Scheme Based on the Polynomial Reconstruction Problem2003
- Bilinear forms over a finite field, with applications to coding theoryJournal of Combinatorial Theory, Series A, 1978