Comparison between Separable and Irreducible Goppa Code in McEliece Cryptosystem

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#.

Authors:

• Thuraya M. Qaradaghi
• Newroz N. Abdulrazaq

Keywords:

• McEliece cryptosystem
• Goppa code
• separable
• irreducible.

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.