Quantum Information Set Decoding Algorithms

Abstract : The security of code-based cryptosystems such as the Mc\-Eliece cryptosystem relies primarily on the difficulty of decoding random linear codes. The best decoding algorithms are all improvements of an old algorithm due to Prange: they are known under the name of information set decoding techniques. It is also important to assess the security of such cryptosystems against a quantum computer. This research thread started in \cite{OS09} and the best algorithm to date has been Bernstein's quantising \cite{B10} of the simplest information set decoding algorithm, namely Prange's algorithm. It consists in applying Grover's quantum search to obtain a quadratic speed-up of Prange's algorithm. In this paper, we quantise other information set decoding algorithms by using quantum walk techniques which were devised for the subset-sum problem in \cite{BJLM13}. This results in improving the worst-case complexity of $2^{0.06035n}$ of Bernstein's algorithm to $2^{0.05869n}$ with the best algorithm presented here (where $n$ is the codelength).
Type de document :
Communication dans un congrès
Tanja Lange; Tsuyoshi Takagi. PQCrypto 2017 - The Eighth International Conference on Post-Quantum Cryptography, Jun 2017, Utrecht, Netherlands. Springer, 10346, pp.69-89, LNCS - Lecture Notes in Computer Science. 〈10.1007/978-3-319-59879-6_5〉
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01661905
Contributeur : Jean-Pierre Tillich <>
Soumis le : mardi 12 décembre 2017 - 14:16:28
Dernière modification le : jeudi 26 avril 2018 - 10:27:55

Fichier

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

Identifiants

Collections

Citation

Ghazal Kachigar, Jean-Pierre Tillich. Quantum Information Set Decoding Algorithms. Tanja Lange; Tsuyoshi Takagi. PQCrypto 2017 - The Eighth International Conference on Post-Quantum Cryptography, Jun 2017, Utrecht, Netherlands. Springer, 10346, pp.69-89, LNCS - Lecture Notes in Computer Science. 〈10.1007/978-3-319-59879-6_5〉. 〈hal-01661905〉

Partager

Métriques

Consultations de la notice

192

Téléchargements de fichiers

29