A New Sieving-style Information-set Decoding Algorithm
(2024) In IEEE Transactions on Information Theory p.1-17- 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... (More)
- 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. (Less)
Please use this url to cite or link to this publication:
https://lup.lub.lu.se/record/605508f0-d050-4bb2-8fce-9a74764ee217
- author
- Nguyen, Vu LU ; Johansson, Thomas LU and Guo, Qian LU
- organization
- publishing date
- 2024-09-01
- type
- Contribution to journal
- publication status
- epub
- subject
- in
- IEEE Transactions on Information Theory
- pages
- 16 pages
- publisher
- IEEE - Institute of Electrical and Electronics Engineers Inc.
- external identifiers
-
- scopus:85204168702
- ISSN
- 0018-9448
- DOI
- 10.1109/TIT.2024.3457150
- language
- English
- LU publication?
- yes
- id
- 605508f0-d050-4bb2-8fce-9a74764ee217
- date added to LUP
- 2024-09-16 16:18:05
- date last changed
- 2024-09-27 04:01:22
@article{605508f0-d050-4bb2-8fce-9a74764ee217, 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,<br/>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.}}, author = {{Nguyen, Vu and Johansson, Thomas and Guo, Qian}}, issn = {{0018-9448}}, language = {{eng}}, month = {{09}}, pages = {{1--17}}, publisher = {{IEEE - Institute of Electrical and Electronics Engineers Inc.}}, series = {{IEEE Transactions on Information Theory}}, title = {{A New Sieving-style Information-set Decoding Algorithm}}, url = {{http://dx.doi.org/10.1109/TIT.2024.3457150}}, doi = {{10.1109/TIT.2024.3457150}}, year = {{2024}}, }