Sieving Method for SDP with the Zero Window: An Improvement in Low Memory Environments

Code-based cryptography is a type of post-quantum cryptography, relying on the complexity of the syndrome decoding problem for its security. Information set decoding (ISD) is a well-known method for solving the syndrome decoding problem, based on an algorithm proposed by Prange in 1962. In 1989, Stern introduced a partitioning called zero window to Prange’s method and realized a faster ISD. In 2023, Guo-Johansson-Nguyen proposed a method to apply the sieving method to ISD, which is known as a fast method for solving shortest vector problems. In this study, we propose a method that introduces the zero window for ISD using the sieving method and evaluate its computational complexity. The proposed method reduces the time complexity by up to approximately 10 bits compared to the original sieving method for 128-bit secure parameters of the Classic McEliece cipher under memory-saving conditions.