Statistical Decoding

Abstract : The security of code-based cryptography relies primarily on the hardness of generic decoding with linear codes. The best generic decoding algorithms are all improvements of an old algorithm due to Prange: they are known under the name of information set decoding techniques (ISD). A while ago a generic decoding algorithm which does not belong to this family was proposed: statistical decoding. It is a randomized algorithm that requires the computation of a large set of parity-check equations of moderate weight. We solve here several open problems related to this decoding algorithm. We give in particular the asymptotic complexity of this algorithm, give a rather efficient way of computing the parity-check equations needed for it inspired by ISD techniques and give a lower bound on its complexity showing that when it comes to decoding on the Gilbert-Varshamov bound it can never be better than Prange's algorithm.
Type de document :
Communication dans un congrès
ISIT 2017 - IEEE International Symposium on Information Theory, Jun 2017, Aachen, Germany. IEEE, pp.1789--1802, 〈10.1109/ISIT.2017.8006839〉
Liste complète des métadonnées

Littérature citée [11 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01661749
Contributeur : Thomas Debris-Alazard <>
Soumis le : mardi 12 décembre 2017 - 13:24:52
Dernière modification le : jeudi 26 avril 2018 - 10:27:44

Fichier

isitStatDecoding.pdf
Accord explicite pour ce dépôt

Identifiants

Collections

Citation

Thomas Debris-Alazard, Jean-Pierre Tillich. Statistical Decoding. ISIT 2017 - IEEE International Symposium on Information Theory, Jun 2017, Aachen, Germany. IEEE, pp.1789--1802, 〈10.1109/ISIT.2017.8006839〉. 〈hal-01661749〉

Partager

Métriques

Consultations de la notice

104

Téléchargements de fichiers

56