An Adaptive Generic Improvement to Information Set Decoding
摘要
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.