Quantum Information Set Decoding Algorithms
Open accessThe DOI matches its Crossref record; 8 of the 8 references it cites were found in a registry or an index.
Abstract
The security of code-based cryptosystems such as the McEliece cryptosystem relies primarily on the difficulty of decoding random linear codes. The best decoding algorithms are all improvements of an old algorithm due to Prange: they are known under the name of information set decoding techniques. It is also important to assess the security of such cryptosystems against a quantum computer. This research thread started in [23] and the best algorithm to date has been Bernstein’s quantising [5] of the simplest information set decoding algorithm, namely Prange’s algorithm. It consists in applying Grover’s quantum search to obtain a quadratic speed-up of Prange’s algorithm. In this paper, we quantise other information set decoding algorithms by using quantum walk techniques which were devised for the subset-sum problem in [6]. This results in improving the worst-case complexity of \(2^{0.06035n}\) of Bernstein’s algorithm to \(2^{0.05869n}\) with the best algorithm presented here (where n is the codelength).
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
A fast quantum mechanical algorithm for database search
Grover, L. K. (1996) · Proceedings of the twenty-eighth annual ACM symposium on Theory of computing - STOC '96 · doi:10.1145/237814.237866 · Cited by 8,830
Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer
Shor, P. W. (1997) · SIAM Journal on Computing · doi:10.1137/s0097539795293172 · Cited by 8,472
(2004) · doi:10.1109/focs.2004.53 · Cited by 599
A method for finding codewords of small weight
Stern, J. (2006) · Lecture Notes in Computer Science · doi:10.1007/bfb0019850 · Cited by 464 · cited 2×
“This problem has been studied since the sixties and despite significant efforts on this issue [22, 26, 10, 2, 17, 7, 4, 18] the best algorithms for solving this problem [4, 18] are exponential in the number of errors that have to be corrected: correcting w errors in a binary linear code of length n…”
BackgroundMethodThe use of information sets in decoding cyclic codes
Prange, E. (1962) · IEEE Transactions on Information Theory · doi:10.1109/tit.1962.1057777 · Cited by 463 · cited 14×
“This problem has been studied since the Sixties and despite significant efforts on this issue [23, 27, 11, 2, 18, 7, 4, 19] the best algorithms for solving this problem [4, 19] are exponential in the number of errors that have to be corrected: correcting w errors in a binary linear code of length n and dimension k has…”
BackgroundMethodInfluentialQuantum Computers Can Search Arbitrarily Large Databases by a Single Query
Grover, L. K. (1997) · Physical Review Letters · doi:10.1103/physrevlett.79.4709 · Cited by 432
Decoding Random Binary Linear Codes in 2 n/20: How 1 + 1 = 0 Improves Information Set Decoding
Becker, A., Joux, A., May, A., & Meurer, A. (2012) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-29011-4_31 · Cited by 398 · cited 9×
“This problem has been studied since the Sixties and despite significant efforts on this issue [23, 27, 11, 2, 18, 7, 4, 19] the best algorithms for solving this problem [4, 19] are exponential in the number of errors that have to be corrected: correcting w errors in a binary linear code of length n and dimension k has…”
BackgroundMethodInfluentialSmaller Decoding Exponents: Ball-Collision Decoding
Bernstein, D. J., Lange, T., & Peters, C. (2011) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-22792-9_42 · Cited by 191
Cited by
Status report on the third round of the NIST Post-Quantum Cryptography Standardization process
Alagic, G., Apon, D., Cooper, D., Dang, Q., Dang, T., Kelsey, J., Lichtinger, J., Liu, Y.-K., Miller, C., Moody, D., et al. (2022) · doi:10.6028/nist.ir.8413 · Cited by 395
Status report on the third round of the NIST Post-Quantum Cryptography Standardization process
Alagic, G., Apon, D., Cooper, D., Dang, Q., Dang, T., Kelsey, J., Lichtinger, J., Liu, Y.-K., Miller, C., Moody, D., et al. (2022) · doi:10.6028/nist.ir.8413-upd1 · Cited by 301
(2017) · Lecture Notes in Computer Science · doi:10.1007/978-3-319-59879-6 · Cited by 20
Quantum CNOT Circuits Synthesis for NISQ Architectures Using the Syndrome Decoding Problem
de Brugière, T. G., Baboulin, M., Valiron, B., Martiel, S., & Allouche, C. (2020) · Lecture Notes in Computer Science · doi:10.1007/978-3-030-52482-1_11 · Cited by 18
On the dimension and structure of the square of the dual of a Goppa code
Mora, R., & Tillich, J.-P. (2023) · Designs, Codes and Cryptography · doi:10.1007/s10623-022-01153-w · Cited by 18
Self-citation
Metadata
- Authors
- Kachigar, G., & Tillich, J.-P.
- Venue
- Lecture Notes in Computer Science
- Publisher
- Springer International Publishing
- Published
- 2017
- Pages
- 69-89
- ISSN
- 0302-9743 (ISSN-L)
- 1611-3349
- OpenAlex
- W2591819627
- Cited by
- 69
- References
- 8
- FWCI
- 2.67
- Type
- conference paper
- Language
- en
- Open access
- green
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: Quantum Information Set Decoding Algorithms. https://app.cochat.ai/papers/10.1007/978-3-319-59879-6_5
- The paper
- Kachigar, G., & Tillich, J.-P. (2017). Quantum Information Set Decoding Algorithms. Lecture Notes in Computer Science. https://doi.org/10.1007/978-3-319-59879-6_5
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.