Computational & Technology Resources
an online resource for computational,
engineering & technology publications
PROCEEDINGS OF THE SEVENTH INTERNATIONAL CONFERENCE ON ENGINEERING COMPUTATIONAL TECHNOLOGY
Edited by: B.H.V. Topping, J.M. Adam, F.J. Pallarés, R. Bru and M.L. Romero
The Computation of an Input-State-Output Realization of a Convolutional Code in order to obtain a Secure McEliece-like Cryptosystem
J.J. Climent1, M.V. Herranz2, C. Perea2 and V. Tomás1
1Department of Statistics and Operations Research, University of Alicante, Spain
J.J. Climent, M.V. Herranz, C. Perea, V. Tomás, "The Computation of an Input-State-Output Realization of a Convolutional Code in order to obtain a Secure McEliece-like Cryptosystem", in B.H.V. Topping, J.M. Adam, F.J. Pallarés, R. Bru, M.L. Romero, (Editors), "Proceedings of the Seventh International Conference on Engineering Computational Technology", Civil-Comp Press, Stirlingshire, UK, Paper 20, 2010. doi:10.4203/ccp.94.20
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 . 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 .
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  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  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.
purchase the full-text of this paper (price £20)