Analysis of Information Set Decoding for a Sub-linear Error Weight

Abstract : The security of code-based cryptography is strongly related to the hardness of generic decoding of linear codes. The best known generic decoding algorithms all derive from the Information Set Decoding algorithm proposed by Prange in 1962. When the number of errors w is sub-linear, w = o(n), the cost of all ISD variants has the form 2^{cw(1+o(1))}. We prove here that the constant c only depends of the code rate k=n and is the same for recent known ISD variants, including the fifty years old Prange algorithm. The most promising variants of McEliece encryption scheme use either Goppa codes, with w = O(n/ log(n)), or MDPC codes, with w = O(n^{1/2}). Our result means that, in those cases, when we scale up the system parameters, the improvement of the latest variants of ISD become less and less signi cant.
Type de document :
Communication dans un congrès
Post-Quantum Cryptography - PQCrypto 2016, Feb 2016, Fukuoka, Japan. 2016
Liste complète des métadonnées


https://hal.inria.fr/hal-01244886
Contributeur : Rodolfo Canto Torres <>
Soumis le : mercredi 16 mars 2016 - 14:21:14
Dernière modification le : mardi 25 juillet 2017 - 10:31:20
Document(s) archivé(s) le : vendredi 17 juin 2016 - 10:38:37

Fichier

sublinearISD.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01244886, version 2

Collections

Citation

Rodolfo Canto Torres, Nicolas Sendrier. Analysis of Information Set Decoding for a Sub-linear Error Weight. Post-Quantum Cryptography - PQCrypto 2016, Feb 2016, Fukuoka, Japan. 2016. <hal-01244886v2>

Partager

Métriques

Consultations de
la notice

243

Téléchargements du document

254