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