The hardness of the syndrome decoding problem (SDP) isthe primary evidence for the security of code-based cryptosystems, whichare one of the finalists in a project to standardize post-quantum cryptographyconducted by the U.S. National Institute of Standards and Technology(NIST-PQC). Information set decoding (ISD) is a general term for algorithmsthat solve SDP efficiently. In this paper, we conducted a concreteanalysis of the time complexity of the latest ISD algorithms under the limitationof memory using the syndrome decoding estimator proposed by Esseret al. As a result, we present that theoretically nonoptimal ISDs, such asMay–Meurer–Thomae (MMT) and May–Ozerov, have lower time complexitythan other ISDs in some actual SDP instances. Based on these facts,we further studied the possibility of multiple parallelization for these ISDsand proposed the first GPU algorithm for MMT, the multiparallel MMTalgorithm. In the experiments, we show that the multiparallel MMT algorithmis faster than existing ISD algorithms. In addition, we report the firstsuccessful attempts to solve the 510-, 530-, 540- and 550-dimensional SDPinstances in the Decoding Challenge contest using the multiparallel MMT
展开▼
