Distinguisher-based attacks on public-key cryptosystems using Reed-Solomon codes
From MaRDI portal
Publication:398980
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.
Recommendations
Cites work
- scientific article; zbMATH DE number 3989251 (Why is no real title available?)
- scientific article; zbMATH DE number 177617 (Why is no real title available?)
- scientific article; zbMATH DE number 3577144 (Why is no real title available?)
- A Distinguisher for High-Rate McEliece Cryptosystems
- A characterization of MDS codes that have an error correcting pair
- A public-key cryptosystem based on binary Reed-Muller codes
- Asymptotically Good Ideal Linear Secret Sharing with Strong Multiplication over Any Fixed Finite Field
- Cryptanalysis of the Niederreiter public key scheme based on GRS subcodes
- Cryptanalysis of the Sidelnikov Cryptosystem
- Enhanced public key security for the McEliece cryptosystem
- Fundamentals of Error-Correcting Codes
- How to mask the structure of codes for a cryptographic use
- On decoding by error location and dependent sets of error positions
- On the edge-independence number and edge-covering number for regular graphs
- On the unique representation of very strong algebraic geometry codes
- Polynomial time attack on wild McEliece over quadratic extensions
- The Magma algebra system. I: The user language
- The non-gap sequence of a subcode of a generalized Reed-Solomon code
- Weak keys in the McEliece public-key cryptosystem
- When Homomorphism Becomes a Liability
- Wild McEliece
Cited in
(32)- A class of double-twisted generalized Reed-Solomon codes
- Designing a Public Key Cryptosystem Based on Quasi-cyclic Subspace Subcodes of Reed-Solomon Codes
- Enhanced public key security for the McEliece cryptosystem
- Square code attack on a modified Sidelnikov cryptosystem
- MDS and near-MDS codes via twisted Reed-Solomon codes
- Quantum resistant public key encryption scheme polarRLCE
- A side-channel attack against \textit{Classic McEliece} when loading the Goppa polynomial
- Cryptanalysis of a system based on twisted Reed-Solomon codes
- Two modifications for Loidreau's code-based cryptosystem
- On the structural security of a McEliece-type cryptosystem based on the sum of tensor products of binary Reed - Muller codes
- A Hadamard product of linear codes: algebraic properties and algorithms for calculating it
- Properties of constacyclic codes under the Schur product
- A new approach based on quadratic forms to attack the McEliece cryptosystem
- The quadratic hull of a code and the geometric view on multiplication algorithms
- A new McEliece-type cryptosystem using Gabidulin-Kronecker product codes
- Structural attacks for public key cryptosystems based on Gabidulin codes
- Classification of Hadamard products of one-codimensional subcodes of Reed-Muller codes
- Injective rank metric trapdoor functions with homogeneous errors
- On the security of a Loidreau rank metric code based encryption scheme
- Encryption scheme based on expanded Reed-Solomon codes
- The syndromes decoding algorithm in group codes
- Polynomial-time key recovery attack on the Faure-Loidreau scheme based on Gabidulin codes
- Cryptanalysis of public-key cryptosystems that use subcodes of algebraic geometry codes
- On linear codes with random multiplier vectors and the maximum trace dimension property
- On ideals in group algebras: an uncertainty principle and the Schur product
- Blockwise rank decoding problem and LRPC codes: cryptosystems with smaller sizes
- On the dimension and structure of the square of the dual of a Goppa code
- Performance bounds for QC-MDPC codes decoders
- Revisiting algebraic attacks on MinRank and on the rank decoding problem
- Distinguishing and recovering generalized linearized Reed-Solomon codes
- Structural properties of self-dual monomial codes with application to code-based cryptography
- Application of one method of linear code recognition to the wire-TAP channel
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)
