An Adaptive Generic Improvement to Information Set Decoding

Sayantan Chatterjee

doi:10.1007/978-981-96-6941-7_28

An Adaptive Generic Improvement to Information Set Decoding

2026-01-01

0

PRE

AI

S

Sayantan Chatterjee *

B

Bhaskar Biswas

DOI：10.1007/978-981-96-6941-7_28

Original

Original request for help

Save

Abstract

En 中文

Code-based cryptography studies cryptosystems which use error-correcting codes. The syndrome decoding problem (SDP) is a hard problem which underlie many code-based cryptosystems. The Information Set Decoding (ISD) is a probabilistic algorithm which solves the syndrome decoding problem more efficiently than brute-force search. Many variants of this algorithm have been proposed over the years (1962-). The variants of Information Set Decoding (ISD) algorithms are the most efficient generic cryptanalysis techniques involving code-based cryptography. In this article, we propose a generic improvement applicable to most of the variants of ISD. We achieve this improvement by translating certain bit operations to finite field operations. The proposal can reduce the time complexity of ISD by polynomial-factor. We provide detailed cost analysis of a ISD variant and compare it to the cost of our modification. Our analysis shows that the modified variant outperforms the unmodified algorithm. In addition, we outline a generic adaptive mechanism which improves the efficiency of almost all ISD algorithms.

Keywords:

Code-based cryptography

Computational syndrome decoding

Information Set Decoding

Post quantum cryptography

An Adaptive Generic Improvement to Information Set Decoding

Abstract

Journal

Organization