Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

A New Sieving-style Information-set Decoding Algorithm

Nguyen, Vu LU orcid ; Johansson, Thomas LU orcid and Guo, Qian LU (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:
author
; and
organization
publishing date
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.
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-16 16:25:12
@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}},
}