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

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 pr...

Descripción completa

Detalles Bibliográficos
Autores Principales: Couvreur, Alain, Gaborit, Philippe, Gauthier-Umaña, Valérie, Otmani, Ayoub, Tillich, Jean-Pierre
Formato: Artículo (Article)
Lenguaje:Inglés (English)
Publicado: Kluwer Academic Publishers 2014
Materias:
Acceso en línea:https://repository.urosario.edu.co/handle/10336/23845
https://doi.org/10.1007/s10623-014-9967-z
id ir-10336-23845
recordtype dspace
spelling ir-10336-238452022-05-02T12:37:16Z 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 Matrix algebra Public key cryptography Recovery Reed-Solomon codes Code-based cryptography Distinguishers Generalized reed-solomon codes Ho-momorphic encryptions Key-recovery Codes (symbols) Code-based cryptography Distinguisher Generalized Reed-Solomon codes Homomorphic encryption Key-recovery 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. 2014 2020-05-26T00:05:58Z info:eu-repo/semantics/article info:eu-repo/semantics/publishedVersion 09251022 15737586 https://repository.urosario.edu.co/handle/10336/23845 https://doi.org/10.1007/s10623-014-9967-z eng info:eu-repo/semantics/openAccess application/pdf Kluwer Academic Publishers instname:Universidad del Rosario
institution EdocUR - Universidad del Rosario
collection DSpace
language Inglés (English)
topic Matrix algebra
Public key cryptography
Recovery
Reed-Solomon codes
Code-based cryptography
Distinguishers
Generalized reed-solomon codes
Ho-momorphic encryptions
Key-recovery
Codes (symbols)
Code-based cryptography
Distinguisher
Generalized Reed-Solomon codes
Homomorphic encryption
Key-recovery
spellingShingle Matrix algebra
Public key cryptography
Recovery
Reed-Solomon codes
Code-based cryptography
Distinguishers
Generalized reed-solomon codes
Ho-momorphic encryptions
Key-recovery
Codes (symbols)
Code-based cryptography
Distinguisher
Generalized Reed-Solomon codes
Homomorphic encryption
Key-recovery
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
description 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.
format Artículo (Article)
author Couvreur, Alain
Gaborit, Philippe
Gauthier-Umaña, Valérie
Otmani, Ayoub
Tillich, Jean-Pierre
author_facet Couvreur, Alain
Gaborit, Philippe
Gauthier-Umaña, Valérie
Otmani, Ayoub
Tillich, Jean-Pierre
author_sort Couvreur, Alain
title Distinguisher-based attacks on public-key cryptosystems using Reed-Solomon codes
title_short Distinguisher-based attacks on public-key cryptosystems using Reed-Solomon codes
title_full Distinguisher-based attacks on public-key cryptosystems using Reed-Solomon codes
title_fullStr Distinguisher-based attacks on public-key cryptosystems using Reed-Solomon codes
title_full_unstemmed Distinguisher-based attacks on public-key cryptosystems using Reed-Solomon codes
title_sort distinguisher-based attacks on public-key cryptosystems using reed-solomon codes
publisher Kluwer Academic Publishers
publishDate 2014
url https://repository.urosario.edu.co/handle/10336/23845
https://doi.org/10.1007/s10623-014-9967-z
_version_ 1740172318909399040
score 12,131701