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

Full description

Autores:
Tipo de recurso:
Fecha de publicación:
2014
Institución:
Universidad del Rosario
Repositorio:
Repositorio EdocUR - U. Rosario
Idioma:
eng
OAI Identifier:
oai:repository.urosario.edu.co:10336/23845
Acceso en línea:
https://doi.org/10.1007/s10623-014-9967-z
https://repository.urosario.edu.co/handle/10336/23845
Palabra clave:
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
Rights
License
Abierto (Texto Completo)
id EDOCUR2_b10c293eb436625680d7ffe230731938
oai_identifier_str oai:repository.urosario.edu.co:10336/23845
network_acronym_str EDOCUR2
network_name_str Repositorio EdocUR - U. Rosario
repository_id_str
spelling 6085bef2-c2bd-476d-9acf-f795decae1979b427099-8a11-435a-9243-2df7721a574052929478600047fac0e-2019-4697-8667-c046cdc3bd08835dac5e-170c-437e-8a29-07fb73acafc02020-05-26T00:05:58Z2020-05-26T00:05:58Z2014Because 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.application/pdfhttps://doi.org/10.1007/s10623-014-9967-z0925102215737586https://repository.urosario.edu.co/handle/10336/23845engKluwer Academic Publishers666No. 2641Designs, Codes, and CryptographyVol. 73Designs, Codes, and Cryptography, ISSN:09251022, 15737586, Vol.73, No.2 (2014); pp. 641-666https://www.scopus.com/inward/record.uri?eid=2-s2.0-84905217777&doi=10.1007%2fs10623-014-9967-z&partnerID=40&md5=2d3741ccd9d58ebce49f8a5319179270Abierto (Texto Completo)http://purl.org/coar/access_right/c_abf2instname:Universidad del Rosarioreponame:Repositorio Institucional EdocURMatrix algebraPublic key cryptographyRecoveryReed-Solomon codesCode-based cryptographyDistinguishersGeneralized reed-solomon codesHo-momorphic encryptionsKey-recoveryCodes (symbols)Code-based cryptographyDistinguisherGeneralized Reed-Solomon codesHomomorphic encryptionKey-recoveryDistinguisher-based attacks on public-key cryptosystems using Reed-Solomon codesarticleArtículohttp://purl.org/coar/version/c_970fb48d4fbd8a85http://purl.org/coar/resource_type/c_6501Couvreur, AlainGaborit, PhilippeGauthier-Umaña, ValérieOtmani, AyoubTillich, Jean-PierreORIGINAL10-1-1-402-9436.pdfapplication/pdf430959https://repository.urosario.edu.co/bitstreams/581487aa-99a6-46dd-803f-cd0e6d6d43ac/download5e904f524fb14ace3f9e502e63138f3dMD51TEXT10-1-1-402-9436.pdf.txt10-1-1-402-9436.pdf.txtExtracted texttext/plain41977https://repository.urosario.edu.co/bitstreams/2d0349f7-ba2c-4253-b5d1-18ee780fc6a6/download8e549c415d24880b12b0ffc39046adafMD52THUMBNAIL10-1-1-402-9436.pdf.jpg10-1-1-402-9436.pdf.jpgGenerated Thumbnailimage/jpeg4609https://repository.urosario.edu.co/bitstreams/79996f25-bb5d-46a9-8bbe-62d5594026b3/download36719fc03f61086a63143bf2fedb4c48MD5310336/23845oai:repository.urosario.edu.co:10336/238452022-05-02 07:37:16.19004https://repository.urosario.edu.coRepositorio institucional EdocURedocur@urosario.edu.co
dc.title.spa.fl_str_mv Distinguisher-based attacks on public-key cryptosystems using Reed-Solomon codes
title Distinguisher-based attacks on public-key cryptosystems using Reed-Solomon codes
spellingShingle Distinguisher-based attacks on public-key cryptosystems using Reed-Solomon codes
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
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
dc.subject.keyword.spa.fl_str_mv 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
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
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.
publishDate 2014
dc.date.created.spa.fl_str_mv 2014
dc.date.accessioned.none.fl_str_mv 2020-05-26T00:05:58Z
dc.date.available.none.fl_str_mv 2020-05-26T00:05:58Z
dc.type.eng.fl_str_mv article
dc.type.coarversion.fl_str_mv http://purl.org/coar/version/c_970fb48d4fbd8a85
dc.type.coar.fl_str_mv http://purl.org/coar/resource_type/c_6501
dc.type.spa.spa.fl_str_mv Artículo
dc.identifier.doi.none.fl_str_mv https://doi.org/10.1007/s10623-014-9967-z
dc.identifier.issn.none.fl_str_mv 09251022
15737586
dc.identifier.uri.none.fl_str_mv https://repository.urosario.edu.co/handle/10336/23845
url https://doi.org/10.1007/s10623-014-9967-z
https://repository.urosario.edu.co/handle/10336/23845
identifier_str_mv 09251022
15737586
dc.language.iso.spa.fl_str_mv eng
language eng
dc.relation.citationEndPage.none.fl_str_mv 666
dc.relation.citationIssue.none.fl_str_mv No. 2
dc.relation.citationStartPage.none.fl_str_mv 641
dc.relation.citationTitle.none.fl_str_mv Designs, Codes, and Cryptography
dc.relation.citationVolume.none.fl_str_mv Vol. 73
dc.relation.ispartof.spa.fl_str_mv Designs, Codes, and Cryptography, ISSN:09251022, 15737586, Vol.73, No.2 (2014); pp. 641-666
dc.relation.uri.spa.fl_str_mv https://www.scopus.com/inward/record.uri?eid=2-s2.0-84905217777&doi=10.1007%2fs10623-014-9967-z&partnerID=40&md5=2d3741ccd9d58ebce49f8a5319179270
dc.rights.coar.fl_str_mv http://purl.org/coar/access_right/c_abf2
dc.rights.acceso.spa.fl_str_mv Abierto (Texto Completo)
rights_invalid_str_mv Abierto (Texto Completo)
http://purl.org/coar/access_right/c_abf2
dc.format.mimetype.none.fl_str_mv application/pdf
dc.publisher.spa.fl_str_mv Kluwer Academic Publishers
institution Universidad del Rosario
dc.source.instname.spa.fl_str_mv instname:Universidad del Rosario
dc.source.reponame.spa.fl_str_mv reponame:Repositorio Institucional EdocUR
bitstream.url.fl_str_mv https://repository.urosario.edu.co/bitstreams/581487aa-99a6-46dd-803f-cd0e6d6d43ac/download
https://repository.urosario.edu.co/bitstreams/2d0349f7-ba2c-4253-b5d1-18ee780fc6a6/download
https://repository.urosario.edu.co/bitstreams/79996f25-bb5d-46a9-8bbe-62d5594026b3/download
bitstream.checksum.fl_str_mv 5e904f524fb14ace3f9e502e63138f3d
8e549c415d24880b12b0ffc39046adaf
36719fc03f61086a63143bf2fedb4c48
bitstream.checksumAlgorithm.fl_str_mv MD5
MD5
MD5
repository.name.fl_str_mv Repositorio institucional EdocUR
repository.mail.fl_str_mv edocur@urosario.edu.co
_version_ 1814167514189398016