Comparison between Separable and Irreducible Goppa Code in McEliece Cryptosystem

Authors: Thuraya M. Qaradaghi, Newroz N. Abdulrazaq

Abstract:

The McEliece cryptosystem is an asymmetric type of cryptography based on error correction code. The classical McEliece used irreducible binary Goppa code which considered unbreakable until now especially with parameter [1024, 524, and 101], but it is suffering from large public key matrix which leads to be difficult to be used practically. In this work Irreducible and Separable Goppa codes have been introduced. The Irreducible and Separable Goppa codes used are with flexible parameters and dynamic error vectors. A Comparison between Separable and Irreducible Goppa code in McEliece Cryptosystem has been done. For encryption stage, to get better result for comparison, two types of testing have been chosen; in the first one the random message is constant while the parameters of Goppa code have been changed. But for the second test, the parameters of Goppa code are constant (m=8 and t=10) while the random message have been changed. The results show that the time needed to calculate parity check matrix in separable are higher than the one for irreducible McEliece cryptosystem, which is considered expected results due to calculate extra parity check matrix in decryption process for g2(z) in separable type, and the time needed to execute error locator in decryption stage in separable type is better than the time needed to calculate it in irreducible type. The proposed implementation has been done by Visual studio C#.

Keywords: McEliece cryptosystem, Goppa code, separable, irreducible.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1338472

References:

[1] R. McEliece. A Public-Key Cryptosystem Based on Algebraic Coding Theory.Technical report, NASA, 1978.
[2] M. Baldi, M. Bianchi, F. Chiaraluce, J. Rosenthal, D. Schipani. A Variant of the McEliece Cryptosystem with Increased Public Key Security. Workshop on Coding and Cryptography WCC 2011, pages 173-182, Paris, France, Apr. 2011.
[3] M. Baldi, F. Chiaraluce, R. Garello, and F. Mininni. Quasi-Cyclic Low- Density Parity-Check Codes in the McEliece Cryptosystem. In ICC, pages 951-956. IEEE, 2007.
[4] T. P. Berger, P.-L. Cayrel, P. Gaborit, and A. Otmani. Reducing Key Length of the McEliece Cryptosystem. In B. Preneel, editor, AFRICACRYPT, volume 5580 of Lecture Notes in Computer Science, pages 77-97. Springer, 2009.
[5] Edoardo Persichetti, Compact McEliece Keys Based on Quasi-Dyadic Srivastava Codes. IACR Cryptology ePrint Archive, 2011 (preprint).
[6] E. M. Gabidulin, A. V. Ourivski, B. Honary, and B. Ammar. Reducible rank codesand their applications to cryptography. IEEE Transactions on Information Theory, 49(12):3289-3293, 2003.
[7] E. M. Gabidulin, A. V. Paramonov, and O. V. Tretjakov. Ideals over a Non-Commutative Ring and their Applications in Cryptology. In D. W. Davies, editor EUROCRYPT, volume 547 of Lecture Notes in Computer Science, pages 482-489. Springer, 1991.
[8] R. Misoczki and P. S. L. M. Barreto. Compact McEliece Keys from Goppa Codes. In M. J. Jacobson Jr., V. Rijmen, and R. Safavi-Naini, Selected Areas in Cryptography, volume 5867 of Lecture Notes in Computer Science, pages 376-392. Springer, 2009.
[9] C. Monico, J. Rosenthal, and A. Shokrollahi. Using low density parity check codesin the McEliece cryptosystem. In IEEE International Symposium on Information Theory, ISIT 2000, page 215. IEEE, 2000.
[10] H. Niederreiter. Knapsack-type cryptosystems and algebraic coding theory. Problemsof Control and Information Theory, 15(2):159-166, 1986.
[11] V. M. Sidelnikov. A public-key cryptosystem based on binary Reed- Muller codes.Discrete Mathematics and Applications, 4(3):191-208, 1994.
[12] J. -C. Faug=>re, A. Otmani, L. Perret, and J. -P. Tillich. Algebraic Cryptanalysis of McEliece Variants with Compact Keys. In H. Gilbert, editor, EUROCRYPT, volume 6110 of Lecture Notes in Computer Science, pages 279-298. Springer, 2010.
[13] L. Minder and A. Shokrollahi. Cryptanalysis of the Sidelnikov Cryptosystem. InM. Naor, EUROCRYPT, volume 4515 of Lecture Notes in Computer Science, pages 347-360. Springer, 2007.
[14] R. Overbeck. A New Structural Attack for GPT and Variants. In E. Dawson and S. Vaudenay, editors, Mycrypt, volume 3715 of Lecture Notes in Computer Science, pages 50-63. Springer, 2005.
[15] V. M. Sidelnikov and S. O. Shestakov. On insecurity of cryptosystems based on generalized Reed-Solomon codes. Discrete Mathematics and Applications, 2(4):439-444, 1992.
[16] Repka Marek, McEliece PKC Calculator, Journal of Electrical Engineering, volume 65, Issue 6, 342-984,Nov,2014.
[17] Wade Trappe, Lawrence Washington, Introduction to Cryptography with Coding Theory, 2nd ed., USA Pearson, 2006.