Distinguisher-based attacks on public-key cryptosystems using Reed-Solomon codes
From MaRDI portal
Publication:398980
DOI10.1007/S10623-014-9967-ZzbMATH Open1310.94138DBLPjournals/dcc/CouvreurGGOT14arXiv1307.6458OpenAlexW2111444563WikidataQ62039163 ScholiaQ62039163MaRDI QIDQ398980FDOQ398980
Authors: Alain Couvreur, Philippe Gaborit, Valérie Gauthier-Umaña, Ayoub Otmani, Jean-Pierre Tillich 
Publication date: 18 August 2014
Published in: Designs, Codes and Cryptography (Search for Journal in Brave)
Abstract: Because of their interesting algebraic properties, several authors promote the use of generalized Reed-Solomon codes in cryptography. Niederreiter was the first to suggest an instantiation of his cryptosystem with them but Sidelnikov and Shestakov showed that this choice is insecure. Wieschebrink proposed a variant of the McEliece cryptosystem which consists in concatenating a few random columns to a generator matrix of a secretly chosen generalized Reed-Solomon code. More recently, new schemes appeared which are the homomorphic encryption scheme proposed by Bogdanov and Lee, and a variation of the McEliece cryptosystem proposed by Baldi et extit{al.} which hides the generalized Reed-Solomon code by means of matrices of very low rank. In this work, we show how to mount key-recovery attacks against these public-key encryption schemes. We use the concept of distinguisher which aims at detecting a behavior different from the one that one would expect from a random code. All the distinguishers we have built are based on the notion of component-wise product of codes. It results in a powerful tool that is able to recover the secret structure of codes when they are derived from generalized Reed-Solomon codes. Lastly, we give an alternative to Sidelnikov and Shestakov attack by building a filtration which enables to completely recover the support and the non-zero scalars defining the secret generalized Reed-Solomon code.
Full work available at URL: https://arxiv.org/abs/1307.6458
Recommendations
generalized Reed-Solomon codescode-based cryptographyhomomorphic encryptiondistinguisherkey-recovery
Cryptography (94A60) Geometric methods (including applications of algebraic geometry) applied to coding theory (94B27)
Cites Work
- The Magma algebra system. I: The user language
- On decoding by error location and dependent sets of error positions
- Title not available (Why is that?)
- Fundamentals of Error-Correcting Codes
- Weak keys in the McEliece public-key cryptosystem
- A Distinguisher for High-Rate McEliece Cryptosystems
- How to mask the structure of codes for a cryptographic use
- Enhanced public key security for the McEliece cryptosystem
- A characterization of MDS codes that have an error correcting pair
- Cryptanalysis of the Niederreiter public key scheme based on GRS subcodes
- Title not available (Why is that?)
- On the edge-independence number and edge-covering number for regular graphs
- When Homomorphism Becomes a Liability
- The non-gap sequence of a subcode of a generalized Reed-Solomon code
- On the unique representation of very strong algebraic geometry codes
- Torsion Limits and Riemann-Roch Systems for Function Fields and Applications
- Wild McEliece
- Asymptotically Good Ideal Linear Secret Sharing with Strong Multiplication over Any Fixed Finite Field
- A public-key cryptosystem based on binary Reed-Muller codes
- Title not available (Why is that?)
- Polynomial time attack on wild McEliece over quadratic extensions
- Cryptanalysis of the Sidelnikov Cryptosystem
Cited In (32)
- Enhanced public key security for the McEliece cryptosystem
- Performance bounds for QC-MDPC codes decoders
- A class of double-twisted generalized Reed-Solomon codes
- Quantum Resistant Public Key Encryption Scheme polarRLCE
- On the structural security of a McEliece-type cryptosystem based on the sum of tensor products of binary Reed - Muller codes
- Blockwise rank decoding problem and LRPC codes: cryptosystems with smaller sizes
- MDS and near-MDS codes via twisted Reed-Solomon codes
- Two modifications for Loidreau's code-based cryptosystem
- Encryption scheme based on expanded Reed-Solomon codes
- A new approach based on quadratic forms to attack the McEliece cryptosystem
- Designing a Public Key Cryptosystem Based on Quasi-cyclic Subspace Subcodes of Reed-Solomon Codes
- Polynomial-time key recovery attack on the Faure-Loidreau scheme based on Gabidulin codes
- Structural properties of self-dual monomial codes with application to code-based cryptography
- A side-channel attack against \textit{Classic McEliece} when loading the Goppa polynomial
- APPLICATION OF ONE METHOD OF LINEAR CODE RECOGNITION TO THE WIRE-TAP CHANNEL
- Injective rank metric trapdoor functions with homogeneous errors
- On the security of a Loidreau rank metric code based encryption scheme
- Square code attack on a modified Sidelnikov cryptosystem
- On linear codes with random multiplier vectors and the maximum trace dimension property
- A new McEliece-type cryptosystem using Gabidulin-Kronecker product codes
- Structural attacks for public key cryptosystems based on Gabidulin codes
- The syndromes decoding algorithm in group codes
- The quadratic hull of a code and the geometric view on multiplication algorithms
- On ideals in group algebras: an uncertainty principle and the Schur product
- Cryptanalysis of a system based on twisted Reed-Solomon codes
- Properties of constacyclic codes under the Schur product
- Cryptanalysis of public-key cryptosystems that use subcodes of algebraic geometry codes
- Classification of Hadamard products of one-codimensional subcodes of Reed-Muller codes
- On the dimension and structure of the square of the dual of a Goppa code
- Revisiting algebraic attacks on MinRank and on the rank decoding problem
- A Hadamard product of linear codes: algebraic properties and algorithms for calculating it
- Distinguishing and recovering generalized linearized Reed-Solomon codes
Uses Software
This page was built for publication: Distinguisher-based attacks on public-key cryptosystems using Reed-Solomon codes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q398980)
