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
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.
