Paper 2021/752

Quantum Reduction of Finding Short Code Vectors to the Decoding Problem

Thomas Debris-Alazard
Maxime Remaud
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 always 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 cannot be used, as such, for the reduction with codes. This problem was solved by using instead a truncated Bernoulli distribution.

Available format(s)
Public-key cryptography
Publication info
Quantum ReductionCode-based CryptographyGeneric Decoding Problem
Contact author(s)
thomas debris @ inria fr
maxime remaud @ atos net
jean-pierre tillich @ inria fr
2023-06-02: revised
2021-06-07: received
See all versions
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.