Paper 2021/752

Quantum Reduction of Finding Short Code Vectors to the Decoding Problem

Thomas Debris-Alazard, Maxime Remaud, and Jean-Pierre Tillich


We give a quantum reduction from finding short codewords in a random linear code to decoding for the Hamming metric. This is the first time such a reduction (classical or quantum) has been obtained. Our reduction adapts to linear codes Stehlé-Steinfield-Tanaka-Xagawa’ re-interpretation of Regev’s quantum reduction from finding short lattice vectors to solving the Closest Vector Problem. The Hamming metric is a much coarser metric than the Euclidean metric and this adaptation has needed several new ingredients to make it work. For instance, in order to have a meaningful reduction it is necessary in the Hamming metric to choose a very large decoding radius and this needs in many cases to go beyond the radius where decoding is unique. Another crucial step for the analysis of the reduction is the choice of the errors that are being fed to the decoding algorithm. For lattices, errors are usually sampled according to a Gaussian distribution. However, it turns out that the Bernoulli distribution (the analogue for codes of the Gaussian) is too much spread out and can not be used for the reduction with codes. Instead we choose here the uniform distribution over errors of a fixed weight and bring in orthogonal polynomials tools to perform the analysis and an additional amplitude amplification step to obtain the aforementioned result.

Available format(s)
Public-key cryptography
Publication info
Preprint. MINOR revision.
Quantum ReductionCode-based CryptographyGeneric Decoding Problem
Contact author(s)
thomas debris @ inria fr
jean-pierre tillich @ inria fr
maxime remaud @ atos net
2021-06-07: received
Short URL
Creative Commons Attribution


      author = {Thomas Debris-Alazard and Maxime Remaud and Jean-Pierre Tillich},
      title = {Quantum Reduction of Finding Short Code Vectors to the Decoding Problem},
      howpublished = {Cryptology ePrint Archive, Paper 2021/752},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.