Time Complexity of Syndrome Decoding Problem and Security Analysis of Code-based Signature Scheme

摘要

The syndrome decoding problem (SDP) is one of the most important hardness assumptions in code-based cryptography. To provide security bounds for the design of code-based cryptographic primitives, analysis of the hardness of the SDP is of utmost importance. We analyzed the hardness of the SDP for the entire range of Hamming weight. We are able to construct a polynomial-time algorithm for the SDP instances in the range (n - k)/2 ≤ w ≤ (n + k)/2. Conversely, no polynomial-time algorithm is known for the range 0 < w < (n - k)/2, and we observe that the time complexity of the information set decoding (ISD) algorithm shows an exponential dependency on the Hamming weight w, taking the maximum when w satisfy the equality of Gilbert-Varshamov bound, where n is the length of the codeword, k is the dimension of the code, v is the syndrome and H is the parity check matrix. Finally, the SDP instances, SDP(H,v,w) with (n + k)/2 < w < n are as hard as the instances SDP(H,v,n - w). Furthermore, we show the system parameters for the standard and multisignature versions of a code based signature scheme RaCoSS based on our new insight.