Algebraic Approach for the Reconstruction of Linear and Convolutional Error Correcting Codes

In this paper we present a generic approach for the problem of the blind estimation of the parameters of linear and convolutional error correcting codes. In a non-cooperative context, an adversary has only access to the noised transmission he has intercepted. The intercepter has no knowledge about the parameters used by the legal users. So, before having acess to the information he has first to blindly estimate the parameters of the error correcting code of the communication. The presented approach has the main advantage that the problem of reconstruction of such codes can be expressed in a very simple way. This allows us to evaluate theorical bounds on the complexity of the reconstruction process but also bounds on the estimation rate. We show that some classical reconstruction techniques are optimal and also explain why some of them have theorical complexities greater than these experimentally observed.

• Johann Barbier
• Guillaume Sicot
• Sebastien Houcke

• Blind estimation parameters
• error correcting codes
• non-cooperative context
• reconstruction algorithm

[1] J. Barbier. Reconstruction of turbo-code encoders. In Proc. SPIE Security and Defense, Space Communication Technologies Symposium, volume 5819, pages 463-473 March 28-31 2005.
[2] G. Burel and R. Gautier. Blind estimation of encoder and interleaver characteristics in a non cooperative context. In Proc. IASTED International Conference on Communications, Internet and Information Technology, November, 17-19, 2003.
[3] A. Canteaut and 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 Trans. Inform. Theory, ISIT06, Juilly 2006.
[4] E. Filiol. Reconstruction of convolutional encoders over gf(q). In M. Darnell, editor, Proc. 6th IMA Conference on Cryptography and Coding, number 1355 in Lecture Notes in Computer Science, pages 100-110. Springer Verlag, 1997.
[6] E. Filiol. Reconstruction of punctured convolutional encoders. In T. Fujiwara, editor, Proc. 2000 International Symposium on Information Theory and Applications, pages 4-7. SITA and IEICE Publishing, 2000.
[7] E. Filiol. Techiques de reconstruction en cryptologie et théorie des codes. PhD thesis, INRIA Rocquencourt, France, March 2001.
[8] J.S. Leon. A probabilistic algorithm for computing the minimum weight of large error-correcting codes. IEEE Trans. on Information Theory, IT-34(5), pages 1354-1359, September 1988.
[9] R. Lidl and H. Niederreiter. Finite Fields. Capbridge University Press, 1983.
[10] G. Planquette. Identification de trains binaires codés. PhD thesis, Université de Rennes I, France, December 1996.
[11] B. Rice. Determinind the parameters of a rate 1/n convolutional encoder over gf(q). In Proc. Third International Conference on Finite Fields and Applications, 1995.
[12] G. Sicot and S. Houcke. Blind detection of interleaver parameters. In Proc. ICASSP 2005, 2005.
[13] G. Sicot and S. Houcke. Etude statistique du seuil dans la détection d'entrelaceur. In Proc. GRESTSI 2005, 2005.
[14] G. Sicot and S. Houcke. Theorical study of the performance of a blind interleaver estimator. In Proc. ISIVC 2006, 2006.
[15] J. Stern. A method for finding codewords of small weight. In G. Cohen and J. Wolfmann, editors, Proc. Coding Theory and Applications, number 3888 in Lecture Notes in Computer Science, pages 106-113, Springer Verlag, 1989.
[16] A. Valembois. Détection, reconnaissance et décode de codes linéaires binaires. PhD thesis, Université de Limoges, France, September 2000.
[17] A. Valembois. Detection and recognition of a binary linear code. Discrete Applied Mathematics, (111):199-218, 2001.