A distinguisher for high-rate McEliece cryptosystems

The Goppa Code Distinguishing (GD) problem consists in distinguishing the matrix of a Goppa code from a random matrix. The hardness of this problem is an assumption to prove the security of code-based cryptographic primitives such as McEliece's cryptosystem. Up to now, it is widely believed tha...

Full description

Autores:
Tipo de recurso:
Fecha de publicación:
2013
Institución:
Universidad del Rosario
Repositorio:
Repositorio EdocUR - U. Rosario
Idioma:
eng
OAI Identifier:
oai:repository.urosario.edu.co:10336/27398
Acceso en línea:
https://doi.org/10.1109/TIT.2013.2272036
https://repository.urosario.edu.co/handle/10336/27398
Palabra clave:
Cryptography
Decoding
Polynomials
Linear systems
Generators
Linear codes
Rights
License
Restringido (Acceso a grupos específicos)
id EDOCUR2_7a5e26a2e76fd9591545d40877551152
oai_identifier_str oai:repository.urosario.edu.co:10336/27398
network_acronym_str EDOCUR2
network_name_str Repositorio EdocUR - U. Rosario
repository_id_str
spelling f2728995-91c8-4937-b6d2-887f83c86fff52929478600047fac0e-2019-4697-8667-c046cdc3bd08485959bc-71db-4576-870c-216c519dd4ce835dac5e-170c-437e-8a29-07fb73acafc02020-08-19T14:42:02Z2020-08-19T14:42:02Z2013-07-03The Goppa Code Distinguishing (GD) problem consists in distinguishing the matrix of a Goppa code from a random matrix. The hardness of this problem is an assumption to prove the security of code-based cryptographic primitives such as McEliece's cryptosystem. Up to now, it is widely believed that the GD problem is a hard decision problem. We present the first method allowing to distinguish alternant and Goppa codes over any field. Our technique can solve the GD problem in polynomial time provided that the codes have sufficiently large rates. The key ingredient is an algebraic characterization of the key-recovery problem. The idea is to consider the rank of a linear system which is obtained by linearizing a particular polynomial system describing a key-recovery attack. It appears that this dimension depends on the type of code considered. Explicit formulas derived from extensive experimentations for the rank are provided for “generic” random, alternant, and Goppa codes over any field. Finally, we give theoretical explanations of these formulas in the case of random codes, alternant codes over any field of characteristic two and binary Goppa codes.application/pdfhttps://doi.org/10.1109/TIT.2013.2272036ISSN: 0096-1000EISSN: 2168-2712https://repository.urosario.edu.co/handle/10336/27398engIEEE6844No. 106830IEEE Transactions on Information TheoryVol. 59IEEE Transactions on Information Theory, ISSN: 0096-1000;EISSN: 2168-2712, Vol.59, No.10 (Oct 2013); pp. 6830-6844https://ieeexplore.ieee.org/document/6553164Restringido (Acceso a grupos específicos)http://purl.org/coar/access_right/c_16ecIEEE Transactions on Information Theoryinstname:Universidad del Rosarioreponame:Repositorio Institucional EdocURCryptographyDecodingPolynomialsLinear systemsGeneratorsLinear codesA distinguisher for high-rate McEliece cryptosystemsUn distintivo para los criptosistemas McEliece de alta velocidadarticleArtículohttp://purl.org/coar/version/c_970fb48d4fbd8a85http://purl.org/coar/resource_type/c_6501Faugère, Jean-CharlesGauthier-Umaña, ValérieOtmani, AyoubPerret, LudovicTillich, Jean-Pierre10336/27398oai:repository.urosario.edu.co:10336/273982021-09-01 06:49:49.909https://repository.urosario.edu.coRepositorio institucional EdocURedocur@urosario.edu.co
dc.title.spa.fl_str_mv A distinguisher for high-rate McEliece cryptosystems
dc.title.TranslatedTitle.spa.fl_str_mv Un distintivo para los criptosistemas McEliece de alta velocidad
title A distinguisher for high-rate McEliece cryptosystems
spellingShingle A distinguisher for high-rate McEliece cryptosystems
Cryptography
Decoding
Polynomials
Linear systems
Generators
Linear codes
title_short A distinguisher for high-rate McEliece cryptosystems
title_full A distinguisher for high-rate McEliece cryptosystems
title_fullStr A distinguisher for high-rate McEliece cryptosystems
title_full_unstemmed A distinguisher for high-rate McEliece cryptosystems
title_sort A distinguisher for high-rate McEliece cryptosystems
dc.subject.keyword.spa.fl_str_mv Cryptography
Decoding
Polynomials
Linear systems
Generators
Linear codes
topic Cryptography
Decoding
Polynomials
Linear systems
Generators
Linear codes
description The Goppa Code Distinguishing (GD) problem consists in distinguishing the matrix of a Goppa code from a random matrix. The hardness of this problem is an assumption to prove the security of code-based cryptographic primitives such as McEliece's cryptosystem. Up to now, it is widely believed that the GD problem is a hard decision problem. We present the first method allowing to distinguish alternant and Goppa codes over any field. Our technique can solve the GD problem in polynomial time provided that the codes have sufficiently large rates. The key ingredient is an algebraic characterization of the key-recovery problem. The idea is to consider the rank of a linear system which is obtained by linearizing a particular polynomial system describing a key-recovery attack. It appears that this dimension depends on the type of code considered. Explicit formulas derived from extensive experimentations for the rank are provided for “generic” random, alternant, and Goppa codes over any field. Finally, we give theoretical explanations of these formulas in the case of random codes, alternant codes over any field of characteristic two and binary Goppa codes.
publishDate 2013
dc.date.created.spa.fl_str_mv 2013-07-03
dc.date.accessioned.none.fl_str_mv 2020-08-19T14:42:02Z
dc.date.available.none.fl_str_mv 2020-08-19T14:42:02Z
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.1109/TIT.2013.2272036
dc.identifier.issn.none.fl_str_mv ISSN: 0096-1000
EISSN: 2168-2712
dc.identifier.uri.none.fl_str_mv https://repository.urosario.edu.co/handle/10336/27398
url https://doi.org/10.1109/TIT.2013.2272036
https://repository.urosario.edu.co/handle/10336/27398
identifier_str_mv ISSN: 0096-1000
EISSN: 2168-2712
dc.language.iso.spa.fl_str_mv eng
language eng
dc.relation.citationEndPage.none.fl_str_mv 6844
dc.relation.citationIssue.none.fl_str_mv No. 10
dc.relation.citationStartPage.none.fl_str_mv 6830
dc.relation.citationTitle.none.fl_str_mv IEEE Transactions on Information Theory
dc.relation.citationVolume.none.fl_str_mv Vol. 59
dc.relation.ispartof.spa.fl_str_mv IEEE Transactions on Information Theory, ISSN: 0096-1000;EISSN: 2168-2712, Vol.59, No.10 (Oct 2013); pp. 6830-6844
dc.relation.uri.spa.fl_str_mv https://ieeexplore.ieee.org/document/6553164
dc.rights.coar.fl_str_mv http://purl.org/coar/access_right/c_16ec
dc.rights.acceso.spa.fl_str_mv Restringido (Acceso a grupos específicos)
rights_invalid_str_mv Restringido (Acceso a grupos específicos)
http://purl.org/coar/access_right/c_16ec
dc.format.mimetype.none.fl_str_mv application/pdf
dc.publisher.spa.fl_str_mv IEEE
dc.source.spa.fl_str_mv IEEE Transactions on Information Theory
institution Universidad del Rosario
dc.source.instname.none.fl_str_mv instname:Universidad del Rosario
dc.source.reponame.none.fl_str_mv reponame:Repositorio Institucional EdocUR
repository.name.fl_str_mv Repositorio institucional EdocUR
repository.mail.fl_str_mv edocur@urosario.edu.co
_version_ 1814167737781452800