Paper 2021/752

Quantum Reduction of Finding Short Code Vectors to the Decoding Problem

Thomas Debris-Alazard
Maxime Remaud
Jean-Pierre Tillich
Abstract

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.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint.
Keywords
Quantum ReductionCode-based CryptographyGeneric Decoding Problem
Contact author(s)
thomas debris @ inria fr
maxime remaud @ atos net
jean-pierre tillich @ inria fr
History
2023-06-02: revised
2021-06-07: received
See all versions
Short URL
https://ia.cr/2021/752
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/752,
      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{https://eprint.iacr.org/2021/752}},
      url = {https://eprint.iacr.org/2021/752}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.