Code-based cryptography is an area of post-quantum cryptography. Several code-based candidates compete in the standardization process of the National Institute of Standards and Technology. A common drawback of code-based cryptosystems is their often large public key size. An approach to decrease this size is the usage of convolutional codes. The idea behind this is that the public key sizes scales linearly in the maximum degree of its polynomial entries. However, thus far the complexity of generic attacks has been exponential in the size of the sliding generator or parity-check matrix. We give a framework which allows us to iteratively decode convolutional codes with information-set decoding. This method relies on the choice of several parameters whose choice affects the success probability of the algorithm and the running time, so we give tools to determine whether a choice of parameters is suitable. We also discuss reasons why the algorithm sometimes doesn’t terminate and how to circumvent said issues.
Finally, we use an implementation of our algorithm to attack two cryptosystem based on convolutional codes. For the first cryptosystem, we managed to recover about 74% of messages in our experiment, each in less than 10 hours. For the second proposal, we used our algorithm to give estimates on the running time and success probability. In two cases where the estimate was low we also verified the result by running the full algorithm. 80% of the experiments were successful and they indicate that the algorithm has a complexity significantly below the security estimates provided by the authors.
- Tags
-