Smaller Keys for Code-Based Cryptography: McEliece Cryptosystems with Convolutional Encoders

In this paper we present a novel class of convolutional codes and investigate its use in a variant of the McEliece cryptosystem that possesses several interesting properties, including a reduction of the public key for a given security level. In contrast to the classical McEliece cryptosystems, where block codes are used, we propose the use of a convolutional encoder to be part of the public key. The secret key is constituted by a Generalized Reed-Solomon encoder and two Laurent polynomial matrices that contain large parts that are generated completely at random. Instead of multiplying on the right the GRS encoder by a permutation matrix, it is multiplied by a polynomial matrix with columns having weight zero or at least two. In this setting the message is a sequence of messages instead of a single block message and the errors are added randomly throughout the sequence. We conclude the paper studying its security and presenting several examples.