Distinguisher-based attacks on public-key cryptosystems using Reed-Solomon codes

Alain Couvreur, Philippe Gaborit, Valérie Gauthier-Umaña, Ayoub Otmani, Jean Pierre Tillich

Resultado de la investigación: Contribución a RevistaArtículo

29 Citas (Scopus)

Resumen

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 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. © 2014 Springer Science+Business Media New York.
Idioma originalEnglish (US)
Páginas (desde-hasta)641-666
Número de páginas26
PublicaciónDesigns, Codes, and Cryptography
DOI
EstadoPublished - ene 1 2014

Huella dactilar

Reed-Solomon codes
Reed-Solomon Codes
Public-key Cryptosystem
Cryptography
Attack
Cryptosystem
Homomorphic Encryption
Key Recovery
Public Key Encryption
Filtration
Scalar
Generator
Alternatives
Recovery
Industry

Citar esto

Couvreur, Alain ; Gaborit, Philippe ; Gauthier-Umaña, Valérie ; Otmani, Ayoub ; Tillich, Jean Pierre. / Distinguisher-based attacks on public-key cryptosystems using Reed-Solomon codes. En: Designs, Codes, and Cryptography. 2014 ; pp. 641-666.
@article{5093320a3d584c88bfb913dd546a84b9,
title = "Distinguisher-based attacks on public-key cryptosystems using Reed-Solomon codes",
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 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. {\circledC} 2014 Springer Science+Business Media New York.",
author = "Alain Couvreur and Philippe Gaborit and Val{\'e}rie Gauthier-Uma{\~n}a and Ayoub Otmani and Tillich, {Jean Pierre}",
year = "2014",
month = "1",
day = "1",
doi = "10.1007/s10623-014-9967-z",
language = "English (US)",
pages = "641--666",
journal = "Designs, Codes, and Cryptography",
issn = "0925-1022",
publisher = "Springer Netherlands",

}

Distinguisher-based attacks on public-key cryptosystems using Reed-Solomon codes. / Couvreur, Alain; Gaborit, Philippe; Gauthier-Umaña, Valérie; Otmani, Ayoub; Tillich, Jean Pierre.

En: Designs, Codes, and Cryptography, 01.01.2014, p. 641-666.

Resultado de la investigación: Contribución a RevistaArtículo

TY - JOUR

T1 - Distinguisher-based attacks on public-key cryptosystems using Reed-Solomon codes

AU - Couvreur, Alain

AU - Gaborit, Philippe

AU - Gauthier-Umaña, Valérie

AU - Otmani, Ayoub

AU - Tillich, Jean Pierre

PY - 2014/1/1

Y1 - 2014/1/1

N2 - 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 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. © 2014 Springer Science+Business Media New York.

AB - 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 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. © 2014 Springer Science+Business Media New York.

U2 - 10.1007/s10623-014-9967-z

DO - 10.1007/s10623-014-9967-z

M3 - Article

SP - 641

EP - 666

JO - Designs, Codes, and Cryptography

JF - Designs, Codes, and Cryptography

SN - 0925-1022

ER -