Information-set decoding for convolutional codes

Abstract

In this paper, we present a framework for generic decoding of convolutional codes, which allows us to do cryptanalysis of code-based systems that use convolutional codes as public keys. We then apply this framework to information set decoding, study success probabilities and give tools to choose variables. Finally, we use this to attack two cryptosystems based on convolutional codes. In the case of Bolkema et al. (Variations of the McEliece cryptosystem. In: Algebraic geometry for coding theory and cryptography: IPAM, Los Angeles, CA, Feb 2016. Springer, Cham, pp 129-150, 2017. [https://doi.org/10.1007/978-3-319-63931-4_5]()), our code recovered about 74% of errors in less than 10 h each, and in the case of Almeida et al. (Smaller keys for code-based cryptography: McEliece cryptosystems with convolutional encoders. CoRR abs/2104.06809, 2021. [arXiv: https://arxiv.org/abs/2104.06809v1]()), we give experimental evidence that 80% of the errors can be recovered in times corresponding to about 70 bits of operational security, with some instances being significantly lower.