### Quantum Reduction of Finding Short Code Vectors to the Decoding Problem

Thomas Debris-Alazard, Maxime Remaud, and 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 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)
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
Quantum ReductionCode-based CryptographyGeneric Decoding Problem
Contact author(s)
thomas debris @ inria fr
jean-pierre tillich @ inria fr
maxime remaud @ atos net
History
Short URL
https://ia.cr/2021/752

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.