Paper 2017/213

Quantum Information Set Decoding Algorithms

Ghazal Kachigar and Jean-Pierre Tillich

Abstract

The security of code-based cryptosystems such as the McEliece 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 Overbeck and Sendrier's 2009 survey on code-based cryptography, and the best algorithm to date has been Bernstein's quantising 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 by Bernstein, Jeffery, Lange and Meurer. 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).

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. Minor revision. PQCrypto 2017 (to appear)
Keywords
code-based cryptographyquantum cryptanalysisdecoding algorithm
Contact author(s)
ghazal kachigar @ u-bordeaux fr
History
2017-04-23: revised
2017-03-02: received
See all versions
Short URL
https://ia.cr/2017/213
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/213,
      author = {Ghazal Kachigar and Jean-Pierre Tillich},
      title = {Quantum Information Set Decoding Algorithms},
      howpublished = {Cryptology ePrint Archive, Paper 2017/213},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/213}},
      url = {https://eprint.iacr.org/2017/213}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.