Keywords: convolutional code, McEliece cryptosystem, public key cryptosystem, input-state-output representation, encryption, decryption, maximum distance separable code, Reed Solomon code, controllability.

The search for secure public-key cryptosystems has been one of the most active areas in the field of cryptology. Many of them emerged just after the invention of RSA, but the development of some cryptanalysis methods have finally made most of them insecure. However, the class of public-key cryptosystems based on error-correcting codes still resists crypto-analysis. The idea to use error-correcting codes in order to construct public key cryptosystems was first proposed in 1978 by McEliece [1]. In his original construction, McEliece used Goppa codes, but some other publications suggested the use of different families of error-correcting codes. This cryptosystem consists of using a easily decodable code as private key, but masking it to give a general code as a public key, in order to confront the cryptanalyst with a computationally infeasible problem. The security of this scheme is given by the NP-complexity of decoding general linear block codes [2].

In this work, in order to introduce secure and efficient public key cryptosystems based on error correcting codes, we present one based on McEliece scheme using convolutional codes. Beginning from a controllable and observable convolutional code given by its input-state-output representation, we obtain a block code whose parity check matrix is just the controllability matrix. The private key in McEliece cryptosystem is then replaced in our cryptosystem by the product of a matrix which contains the local description of trajectories matrix of the convolutional code and a generator matrix of the block code obtained above. Rosenthal [3] propose an iterative algebraic decoding algorithm that decodes convolutional codes with a certain underlying algebraic structure. We use this algorithm to complete the decoding of the public key cryptosystem that we propose.

Finally we use some results introduced by Zaballa [4] to get the input-state-output representation matrices of the convolutional code, from the parity check matrix of a maximum distance separable block code. Since maximum distance separable codes have the highest capability to correct errors of all the codes with the same parameters, this allows the sender to introduce as many errors as possible and to make secure the cryptosystem.

1

R.J. McEliece, "A public-key cryptosystem based on algebraic coding theory", DNS Progress Report 42-44, Jet Propulsion Laboratory, 1978.

2

A. Canteaut, F. Chabaud, "A new algorithm for finding minimum-weight words in a linear code: application to McEliece's cryptosystem and to narrow-sense BCH codes of length 511", IEEE Transactions on Information Theory, 44(1), 367-378, 1998. doi:10.1109/ISIT.1997.613255

3

J. Rosenthal, "An algebraic decoding algorithm for convolutional codes", Progress in Systems and Control Theory, 25, 343-360, 1999.

4

I. Zaballa, "On a partial realization problem", preprint.

purchase the full-text of this paper (price £20)

go to the previous paper
go to the next paper
return to the table of contents
return to the book description
purchase this book (price £125 +P&P)