Fetching the paper…
Reading the bibliography…
We give a quantum reduction from finding short codewords in a random linear code to decoding for the Hamming metric.
The use of information sets in decoding cyclic codes
Eugene Prange · 1962
Earlier work this paper cites.
Bounds for unrestricted codes
Philippe Delsarte · 1972
Earlier work this paper cites.
New upper bounds on the rate of a code via the Delsarte-MacWilliams inequalities
R. J. McEliece, E. R. Rodemich, H. Rumsey, and L. R. Welch · 1977
Earlier work this paper cites.
A Public-Key System Based on Algebraic Coding Theory
Robert J. McEliece · 1978
Earlier work this paper cites.
Bounds for packings in n − n- dimensional Euclidean space
Vladimir Iossifovitch Levenshtein · 1979
Earlier work this paper cites.
A method for finding codewords of small weight
Jacques Stern · 1988
Earlier work this paper cites.
Distance-Regular Graphs
Andries E. Brouwer, Arjeh M. Cohen, and Arnold Neumaier · 1989
Earlier work this paper cites.
Two decoding algorithms for linear codes
Il’ya Dumer · 1989
Earlier work this paper cites.
A new identification scheme based on syndrome decoding
Jacques Stern · 1993
Earlier work this paper cites.
Algorithms for quantum computation: Discrete logarithms and factoring
Peter W. Shor · 1994
Earlier work this paper cites.
On the power of quantum computation
Daniel R. Simon · 1994
Earlier work this paper cites.
An efficient pseudo-random generator provably as secure as syndrome decoding
Jean-Bernard Fischer and Jacques Stern · 1996
Earlier work this paper cites.
Association schemes and coding theory
Philippe Delsarte and Vladimir Iossifovitch Levenshtein · 1998
Earlier work this paper cites.
Codes on graphs: Normal realizations
G. David Jr. Forney · 2001
Cited alongside, same era.
New upper bounds on sphere packings I
Henry Cohn and Noam Elkies · 2003
Cited alongside, same era.
A family of fast syndrome based cryptographic hash functions
Daniel Augot, Matthieu Finiasz, and Nicolas Sendrier · 2005
Cited alongside, same era.
On lattices, learning with errors, random linear codes, and cryptography
Oded Regev · 2005
Cited alongside, same era.
Properties of codes in rank metric, 2006
Pierre Loidreau · 2006
Cited alongside, same era.
On lattices, learning with errors, random linear codes, and cryptography
Oded Regev · 2009
Cited alongside, same era.
Low-complexity cryptographic hash functions
Benny Applebaum, Naama Haramaty, Yuval Ishai, Eyal Kushilevitz, and Vinod Vaikuntanathan · 2017
Later among the works it cites.
Decoding linear codes with high error rate and its impact for LPN security
Leif Both and Alexander May · 2018
Later among the works it cites.
Rank quasi cyclic (RQC)
Carlos Aguilar Melchor, Nicolas Aragon, Slim Bettaieb, Loïc Bidoux, Olivier Blazy, Jean-Christophe Deneuville, Philippe Gaborit, Gilles Zémor, Alain Couvreur, and Adrien Hauteville · 2019
Later among the works it cites.
ROLLO (merger of Rank-Ouroboros, LAKE and LOCKER)
Nicolas Aragon, Olivier Blazy, Jean-Christophe Deneuville, Philippe Gaborit, Adrien Hauteville, Olivier Ruatta, Jean-Pierre Tillich, Gilles Zémor, Carlos Aguilar Melchor, Slim Bettaieb, Loïc Bidoux, Magali Bardet, and Ayoub Otmani · 2019
Later among the works it cites.
Improved Veron identification and signature schemes in the rank metric
Emanuele Bellini, Florian Caullery, Philippe Gaborit, Marc Manzano, and Víctor Mateu · 2019
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Damien Stehlé, Ron Steinfeld, Keisuke Tanaka, and Keita Xagawa · 2009
Cited alongside, same era.
More on average case vs approximation complexity
Michael Alekhnovich · 2011
Cited alongside, same era.
Decoding random linear codes in O ( 2 0.054 n ) O(2^{0.054n})
Alexander May, Alexander Meurer, and Enrico Thomae · 2011
Cited alongside, same era.
Decoding random binary linear codes in 2 n / 20 2^{n/20} : How 1 + 1 = 0 1+1=0 improves information set decoding
Anja Becker, Antoine Joux, Alexander May, and Alexander Meurer · 2012
Cited alongside, same era.
MDPC-McEliece: New McEliece variants from moderate density parity-check codes, 2012
Rafael Misoczki, Jean-Pierre Tillich, Nicolas Sendrier, and Paulo S. L. M. Barreto · 2012
Cited alongside, same era.
On computing nearest neighbors with applications to decoding of binary linear codes
Alexander May and Ilya Ozerov · 2015
Cited alongside, same era.
Worst-case hardness for LPN and cryptographic hashing via code smoothing
Zvika Brakerski, Vadim Lyubashevsky, Vinod Vaikuntanathan, and Daniel Wichs · 2019
Later among the works it cites.
Collision resistant hashing from sub-exponential learning parity with noise
Yu Yu, Jiang Zhang, Jian Weng, Chun Guo, and Xiangxue Li · 2019
Later among the works it cites.
Enhancing code based zero-knowledge proofs using rank metric
Emanuele Bellini, Philippe Gaborit, Alexandros Hasikos, and Víctor Mateu · 2020
Later among the works it cites.
Information set decoding in the lee metric with applications to cryptography
Anna-Lena Horlemann-Trautmann and Violetta Weger · 2020
Later among the works it cites.
Statistical decoding 2.0: Reducing decoding to LPN
Kevin Carrier, Thomas Debris-Alazard, Charles Meyer-Hilfiger, and Jean-Pierre Tillich · 2022
Closest in time.
Quantum algorithms for variants of average-case lattice problems via filtering
Yilei Chen, Qipeng Liu, and Mark Zhandry · 2022
Closest in time.
Smoothing codes and lattices: Systematic study and new bounds
Thomas Debris-Alazard, Léo Ducas, Nicolas Resch, and Jean-Pierre Tillich · 2022
Closest in time.
Worst and average case hardness of decoding via smoothing bounds
Thomas Debris-Alazard and Nicolas Resch · 2022
Closest in time.