The DOI matches its Crossref record, with a small difference in title or year; 30 of the 30 references it cites were found in a registry or an index.
A New Sieving-Style Information-Set Decoding Algorithm
Abstract
The problem of decoding random codes is a fundamental problem for code-based cryptography, including recent code-based candidates in the NIST post-quantum standardization process. In this paper, we present a novel Sieving-style Information-set Decoding algorithm, addressing the task of solving the syndrome decoding problem. Our approach involves maintaining a list of weight-$2p$solution vectors to a partial syndrome decoding problem and then creating new vectors by identifying pairs of vectors that collide in p positions. By gradually increasing the parity-check condition by one and repeating this process iteratively, we find the final solution(s). We show that our novel algorithm performs better than other ISDs in the memory-restricted scenario when applied to McEliece. Notably, in the case of problem instances with very low relative weight, the sieving approach uses significantly less memory compared to other ISD algorithms while being competitive in terms of performance.
Overview
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
In the citing paper
“These techniques originated with Prange's algorithm in 1962 [47] and have undergone a series of improvements [48-56].”
From Status report on the fourth round of the NIST post-quantum cryptography standardization process (2025) · cites this paper as [56]
In the citing paper
“Independent estimates [56, 71] of the cost of information set decoding algorithms have long suggested that Classic McEliece's parameter sets (i.e., mceliece460896 and mceliece460896f) that claim Category 3 security fall short of their security target.”
From Status report on the fourth round of the NIST post-quantum cryptography standardization process (2025) · cites this paper as [56]
Citations
Cites
Computational Complexity: A Modern Approach
Arora, S., & Barak, B. (2009) · doi:10.1017/cbo9780511804090 · Cited by 1,690
On the inherent intractability of certain coding problems (Corresp.)
Berlekamp, E., McEliece, R., & van Tilborg, H. (1978) · IEEE Transactions on Information Theory · doi:10.1109/tit.1978.1055873 · Cited by 1,523
A sieve algorithm for the shortest lattice vector problem
Ajtai, M., Kumar, R., & Sivakumar, D. (2001) · Proceedings of the thirty-third annual ACM symposium on Theory of computing · doi:10.1145/380752.380857 · Cited by 558
A method for finding codewords of small weight
Stern, J. (2006) · Lecture Notes in Computer Science · doi:10.1007/bfb0019850 · Cited by 464
The 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
How to Achieve a McEliece-Based Digital Signature Scheme
Courtois, N. T., Finiasz, M., & Sendrier, N. (2001) · Lecture notes in computer science · doi:10.1007/3-540-45682-1_10 · Cited by 440
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
A new identification scheme based on syndrome decoding
Stern, J. (1994) · Lecture notes in computer science · doi:10.1007/3-540-48329-2_2 · Cited by 361
Attacking and Defending the McEliece Cryptosystem
Bernstein, D. J., Lange, T., & Peters, C. (2008) · Lecture notes in computer science · doi:10.1007/978-3-540-88403-3_3 · Cited by 348
An Observation on the Security of McEliece’s Public-Key Cryptosystem
Lee, P. J., & Brickell, E. F. (1988) · Lecture Notes in Computer Science · doi:10.1007/3-540-45961-8_25 · Cited by 290
Security Bounds for the Design of Code-Based Cryptosystems
Finiasz, M., & Sendrier, N. (2009) · Lecture notes in computer science · doi:10.1007/978-3-642-10366-7_6 · Cited by 269
Sieve algorithms for the shortest vector problem are practical
Nguyễn, P. Q., & Vidick, T. (2008) · Journal of Mathematical Cryptology · doi:10.1515/jmc.2008.009 · Cited by 234
A probabilistic algorithm for computing minimum weights of large error-correcting codes
Leon, J. S. (1988) · IEEE Transactions on Information Theory · doi:10.1109/18.21270 · Cited by 224
On Computing Nearest Neighbors with Applications to Decoding of Binary Linear Codes
May, A., & Ozerov, I. (2015) · Lecture notes in computer science · doi:10.1007/978-3-662-46800-5_9 · Cited by 219
Smaller 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
Classic McEliece: conservative code-based cryptography: Round 4 Submission
Albrecht, M. R., Bernstein, D. J., Chou, T., Cid, C., Gilcher, J., Lange, T., Maram, V., von Maurich, I., Misoczki, R., Niederhagen, R., et al. (2022) · HAL · Cited by 145
Sendrier, N. (2011) · Lecture notes in computer science · doi:10.1007/978-3-642-25405-5_4 · Cited by 132
A Family of Fast Syndrome Based Cryptographic Hash Functions
Augot, D., Finiasz, M., & Sendrier, N. (2005) · Lecture notes in computer science · doi:10.1007/11554868_6 · Cited by 116
An Efficient Pseudo-Random Generator Provably as Secure as Syndrome Decoding
Fischer, J.-B., & Stern, J. (1996) · Lecture notes in computer science · doi:10.1007/3-540-68339-9_22 · Cited by 112
Improved identification schemes based on error-correcting codes
Véron, P. (1997) · Applicable Algebra in Engineering Communication and Computing · doi:10.1007/s002000050053 · Cited by 100
Decoding Linear Codes with High Error Rate and Its Impact for LPN Security
Both, L., & May, A. (2018) · Lecture notes in computer science · doi:10.1007/978-3-319-79063-3_2 · Cited by 95
Analysis of Information Set Decoding for a Sub-linear Error Weight
Canto Torres, R., & Sendrier, N. (2016) · Lecture Notes in Computer Science · doi:10.1007/978-3-319-29360-8_10 · Cited by 85
On the complexity of some cryptographic problems based on the general decoding problem
Johansson, T., & Jönsson, F. (2002) · IEEE Transactions on Information Theory · doi:10.1109/tit.2002.802608 · Cited by 50
Self-citationEsser, A., & Bellini, E. (2022) · Lecture notes in computer science · doi:10.1007/978-3-030-97121-2_5 · Cited by 45
A sieve algorithm based on overlattices
Becker, A., Gama, N., & Joux, A. (2014) · LMS Journal of Computation and Mathematics · doi:10.1112/s1461157014000229 · Cited by 44
A Finite Regime Analysis of Information Set Decoding Algorithms
Baldi, M., Barenghi, A., Chiaraluce, F., Pelosi, G., & Santini, P. (2019) · Algorithms · doi:10.3390/a12100209 · Cited by 43
Statistical Decoding 2.0: Reducing Decoding to LPN
Carrier, K., Debris-Alazard, T., Meyer-Hilfiger, C., & Tillich, J. (2022) · Lecture notes in computer science · doi:10.1007/978-3-031-22972-5_17 · Cited by 35
Really Fast Syndrome-Based Hashing
Bernstein, D. J., Lange, T., Peters, C., & Schwabe, P. (2011) · Lecture notes in computer science · doi:10.1007/978-3-642-21969-6_9 · Cited by 34
McEliece Needs a Break – Solving McEliece-1284 and Quasi-Cyclic-2918 with Modern ISD
Esser, A., May, A., & Zweydinger, F. (2022) · Lecture notes in computer science · doi:10.1007/978-3-031-07082-2_16 · Cited by 33
Asymptotics and Improvements of Sieving for Codes
Ducas, L., Esser, A., Etinski, S., & Kirshanova, E. (2024) · Lecture notes in computer science · doi:10.1007/978-3-031-58754-2_6 · Cited by 15
Research works printed but not linked: 7
- 2022, NIST Post-Quantum Cryptography Standardization
- Melchor, 2018, Hamming quasi-cyclic (HQC), NIST PQC Round, 2, 13
- Dumer, On minimum distance decoding of linear codes, 50
- May, Decoding random linear codes in \mathcal{\ {O}}(2^0.054n), 7073, 107
- Both, Optimizing BJMM with nearest neighbors: Full decoding in 22/21n and McEliece security, 214
- Hamdaoui, 2013, A non asymptotic analysis of information set decoding, 162
- Becker, Solving shortest and closest vector problems: The decomposition approach
Cited by
Status report on the fourth round of the NIST post-quantum cryptography standardization process
Alagic, G., Bros, M., Ciadoux, P., Cooper, D., Dang, Q., Dang, T., Kelsey, J., Lichtinger, J., Liu, Y.-K., Miller, C., et al. (2025) · doi:10.6028/nist.ir.8545 · Cited by 211
Metadata
- Authors
- Guo, Q., Johansson, T., & Nguyen, V.
- Affiliations
- Lund University (SE)
- Venue
- IEEE Transactions on Information Theory
- Published
- 2024-11
- Volume
- 70
- Issue
- 11
- Pages
- 8303-8319
- ISSN
- 0018-9448 (ISSN-L)
- 1557-9654
- OpenAlex
- W4402402210
- Cited by
- 12
- References
- 30
- Citations by year
- 2026: 5 · 2025: 2 · 2024: 3
- FWCI
- 1.48
- Type
- journal article
- Language
- en
- Open access
- closed
- Licence
- Locations
- IEEE Transactions on Information Theory (publishedVersion)
- Lund University Publications (Lund University) (submittedVersion)
- Funders
- Swedish Foundation for Strategic Research (RIT17-0005)
- Swedish Research Council (2021-04602)
- Topics
- Physical Sciences › Mathematics › Discrete Mathematics and Combinatorics › Coding theory and cryptography
- Physical Sciences › Computer Science › Information Systems › Cryptography and Residue Arithmetic
- Physical Sciences › Computer Science › Computer Networks and Communications › Error Correcting Code Techniques
- Keywords
- information set decoding, syndrome decoding, code-based cryptography, McEliece cryptosystem, post-quantum cryptography, NIST post-quantum standardization
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
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.
