KACHIGAR, Ghazal; TILLICH, Jean-Pierre

doi:10.1007/978-3-319-59879-6_5

Métadonnées

Afficher la notice complète

Licence d’utilisation du document

KACHIGAR, Ghazal
Security, Cryptology and Transmissions [SECRET]
Institut de Mathématiques de Bordeaux [IMB]

TILLICH, Jean-Pierre
Security, Cryptology and Transmissions [SECRET]

Langue

Communication dans un congrès

Ce document a été publié dans

PQCrypto 2017 - The Eighth International Conference on Post-Quantum Cryptography, 2017-06-26, Utrecht. vol. 10346, p. 69-89

Springer

Résumé en anglais

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 thebest 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).< Réduire

Mots clés en anglais

code based cryptography

decoding algorithms

quantum algorithms

URI

https://oskar-bordeaux.fr/handle/20.500.12278/193466

DOI

http://dx.doi.org/10.1007/978-3-319-59879-6_5

Projet Européen

Post-quantum cryptography for long-term security

Origine

Importé de hal

Unités de recherche

Institut de Mathématiques de Bordeaux (IMB) - UMR 5251