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
N1 - Copyright:
Copyright 2014 Elsevier B.V., All rights reserved.
PY - 2014/11
Y1 - 2014/11
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.
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.
UR - http://www.scopus.com/inward/record.url?scp=84905217777&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84905217777&partnerID=8YFLogxK
U2 - 10.1007/s10623-014-9967-z
DO - 10.1007/s10623-014-9967-z
M3 - Research Article
AN - SCOPUS:84905217777
SN - 0925-1022
VL - 73
SP - 641
EP - 666
JO - Designs, Codes, and Cryptography
JF - Designs, Codes, and Cryptography
IS - 2
ER -