In this talk I will present a quantum reduction from the problem of sampling short vectors in a code to the problem of decoding its dual. Usually codes are endowed with the Hamming metric but as I will show the reduction works for a large class of metrics (including the rank and Lee metrics). Furthermore, in many cases, we are able to show that thanks to a quantum computer solving the decoding problem at distance t we can find short codewords of weight f(t) for some explicit function. Surprisingly, for codes equipped with the Hamming metric the function f is in relationship with the first linear programming bound of McEliece-Redomich-Rumsey-Welch. This result is rather intriguing and does not seem to have a simple interpretation for now.
The main technical tool used in the proof is the discrete Fourier transform. The proof follows the same ideas of Regev’s quantum reduction between the Closest Vector Problem and sampling short lattice vectors. More precisely, the proof I will present uses with codes the same techniques as Stehlé, Steinfeld, Tanaka and Xagawa ’s re-interpretation of Regev’s proof.
This is joint work with Maxime Remaud and Jean-Pierre Tillich
Thomas Debris-Alazard is a research scientist (chargé de recherche) at Inria in the Grace project-team. He was previously a postdoctoral research assistant in the Information Security Group under the supervision of Martin R. Albrecht. He received his PhD from Inria under the supervision of Jean-Pierre Tillich.