Quantum Information Set Decoding Algorithms
KACHIGAR, Ghazal
Security, Cryptology and Transmissions [SECRET]
Institut de Mathématiques de Bordeaux [IMB]
Security, Cryptology and Transmissions [SECRET]
Institut de Mathématiques de Bordeaux [IMB]
KACHIGAR, Ghazal
Security, Cryptology and Transmissions [SECRET]
Institut de Mathématiques de Bordeaux [IMB]
< Reduce
Security, Cryptology and Transmissions [SECRET]
Institut de Mathématiques de Bordeaux [IMB]
Language
en
Communication dans un congrès
This item was published in
PQCrypto 2017 - The Eighth International Conference on Post-Quantum Cryptography, 2017-06-26, Utrecht. vol. 10346, p. 69-89
Springer
English 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 ...Read more >
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).Read less <
English Keywords
code based cryptography
decoding algorithms
quantum algorithms
European Project
Post-quantum cryptography for long-term security
Origin
Hal imported