CODE-BASED HYBRID CRYPTOSYSTEM: COMPARATIVE STUDIES AND ANALYSIS OF EFFICIENCY

Authors

  • Yurii Gorbenko
  • Anastasiia Kiian
  • Andriy Pushkar’ov
  • Oleksandr Korneiko
  • Serhii Smirnov
  • Tetiana Kuznetsova

DOI:

https://doi.org/10.47839/ijc.18.4.1608

Keywords:

Algebraic codes, Code-based cryptography, McEliece cryptosystem, Niederreiter cryptosystem, Public-key cryptosystem, Post-quantum cryptosystem.

Abstract

In this paper the basic principles of construction and operation of McEliece and Niederreiter cryptosystems based on the use of error-correcting codes were considered. A new hybrid cryptosystem that combines the rules of encryption according to the above-mentioned schemes is proposed. Also, this paper presents the analysis and comparative studies from the standpoint of stability, the volume of public and private keys, length of ciphertext and relative speed of information transmission of the new proposed scheme and McEliece and Niederreiter cryptosystems. It is considered from an analytical point of view and with the help of graphic images. Comparative studies revealed that the hybrid cryptosystem retains the positive aspects of its predecessors, as well as allows us to increase the relative transmission rate with the preservation of the stability indicator to the classical and quantum cryptanalysis. One disadvantage is the increase in decoding time by adding information extracted as in Niederreiter scheme, but the increase in this indicator is not critical. Despite the demonstrated benefits, it remains open to all cryptosystems to reduce the amount of the used key data, which, in the case of quantum computers to maintain stability, still needs to be increased once.

References

A.J. Menezes, P.C. van Oorschot, S.A. Vanstone, Handbook of Applied Cryptography, CRC Press, 1997, 794 р.

N. Ferguson and B. Schneier, Practical Cryptography, John Wiley & Sons, 2003, 432 p.

D. Moody, “Post-quntum cryptography: NIST’s plan for the future,” Proceedings of the Seventh International Conference on Post-Quntum Cryptography, Japan, 2016, [Online]. Available at: https://pqcrypto2016.jp

N. Koblitz and A.J. Menezes, “A Riddle wrapped in an enigma,” [Online], Available at: https://eprint.iacr.org/2015/1018.pdf

F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes, North-Holland, Amsterdam, New York, Oxford, 1977, 762 p.

R. J. McEliece, A Public-key Cryptosystem based on Algebraic Coding Theory, DSN Progress Report 42-44, Jet Propulsion Lab., January-February, 1978, pp. 114-116.

S. Heyse, “Implementation of McEliece based on quasi-dyadic Goppa codes for embedded devices,” in Post-Quantum Cryptography, ser. Lecture Notes in Computer Science, B.-Y. Yang, Ed. Springer Berlin / Heidelberg, 2011, vol. 7071, pp. 143-162.

M. Finiasz and N. Sendrier, “Security bounds for the design of codebased cryptosystems,” in M. Matsui, ed., Advances in Cryptology, ASIACRYPT 2009, volume 5912 of Lecture Notes in Computer Science, Springer Berlin Heidelberg, 2009, pp. 88 -105.

N. Courtois, M. Finiasz, and N. Sendrier, “How to achieve a McEliece-based digital signature scheme,” Proceedings of the Advances in Cryptology – ASIACRYPT 2001, vol. 2248, pp. 157–174.

H. Niederreiter, “Knapsack-type cryptosystems and algebraic coding theory,” Problem Control and Inform Theory, vol. 15, pp. 19-34, 1986.

A. Kuznetsov, A. Pushkar’ov, N. Kiyan and T. Kuznetsova, “Code-based electronic digital signature,” Proceedings of the 2018 IEEE 9th International Conference on Dependable Systems, Services and Technologies (DESSERT), Kyiv, Ukraine, 2018, pp. 331-336. DOI: 10.1109/DESSERT.2018.8409154

A. Kuznetsov, M. Lutsenko, N. Kiian, T. Makushenko and T. Kuznetsova, “Code-based key encapsulation mechanisms for post-quantum standardization,” Proceedings of the 2018 IEEE 9th International Conference on Dependable Systems, Services and Technologies (DESSERT), Kyiv, Ukraine, 2018, pp. 276-281. DOI: 10.1109/DESSERT.2018.8409144

A. Kuznetsov, A. Kiian, M. Lutsenko, I. Chepurko and S. Kavun, “Code-based cryptosystems from NIST PQC,” Proceedings of the 2018 IEEE 9th International Conference on Dependable Systems, Services and Technologies (DESSERT), Kyiv, Ukraine, 2018, pp. 282-287. DOI: 10.1109/DESSERT.2018.8409145

Vladimir M. Sidelnikov and Sergey O. Shestakov, “On insecurity of cryptosystems based on generalized Reed-Solomon codes,” Discrete Mathematics and Applications, vol. 2, issue 4, pp. 439-444, 1992.

Y. X. Li, R. H. Deng and X. M. Wang, “On the equivalence of McEliece's and Niederreiter's public-key cryptosystems,” IEEE Transactions on Information Theory, vol. 40, no. 1, pp. 271-273, Jan. 1994.

A. A. Kuznetsov, Yu. І. Gorbenko, D. I. Prokopovych-Tkachenko, М. S. Lutsenko, M. V. Pastukhov. “NIST PQC: Code-based cryptosystems,” Telecommunications and Radio Engineering, vol. 78, issue 5, pp. 429-441, 2019. DOI: 10.1615/TelecomRadEng.v78.i5.50

O. Al Rasheed and P. Ivaniš, “Complexity and performance of QC-MDPC code-based McEliece cryptosystems,” Proceedings of the 2015 12th International Conference on Telecommunication in Modern Satellite, Cable and Broadcasting Services (TELSIKS), Nis, 2015, pp. 31-34. DOI: 10.1109/TELSKS.2015.7357731

M. Baldi, P. Santini and F. Chiaraluce, “Soft McEliece: MDPC code-based McEliece cryptosystems with very compact keys through real-valued intentional errors,” Proceedings of the 2016 IEEE International Symposium on Information Theory (ISIT), Barcelona, 2016, pp. 795-799. DOI: 10.1109/ISIT.2016.7541408

Q. Wang, X. Qiu, Q. Zhang and C. Tang, “Key privacy in McEliece public key cryptosystem,” Proceedings of the 2011 IEEE 10th International Conference on Trust, Security and Privacy in Computing and Communications, Changsha, 2011, pp. 824-828. DOI: 10.1109/TrustCom.2011.109

D. Bernstein, J. Buchmann and E. Dahmen, Post-Quantum Cryptography, Springer-Verlag, Berlin-Heidleberg, 2009, 245 p.

J. Proos and C. Zalka. “Shor's discrete logarithm quantum algorithm for elliptic curves,” Quantum Info. Comput., vol. 3, issue 4, pp. 317-344, 2003.

D.J. Bernstein, T. Lange, C. Peters, “Attacking and defending the McEliece cryptosystem,” in Buchmann J., Ding J. (eds) Post-Quantum Cryptography. PQCrypto 2008. Lecture Notes in Computer Science, vol 5299, Springer, Berlin, Heidelberg, 2008, pp. 31-46.

L. Grover, “A fast quantum mechanical algorithm for database search,” Proceedings of the 28th Annual ACM Symposium on the Theory of Computing (STOC’96), ACM Press, New York, 1996, pp. 212-219.

N. Sendrier, “Decoding one out of many,” in Yang, B.Y., ed.: PQCrypto 2011, volume 7071 of LNCS, Springer, 2011, pp. 51-67.

S. H. Odin Hashemi and G. A. Hodtani, “A modified McEliece public-key cryptosystem based on irregular codes of QC-LDPC and QC-MDPC,” Proceedings of the 2019 27th Iranian Conference on Electrical Engineering (ICEE), Yazd, Iran, 2019, pp. 1373-1376. DOI: 10.1109/IranianCEE.2019.8786376

F. P. Biasi, P. S. L. M. Barreto, R. Misoczki, W. V. Ruggiero, “Scaling efficient code-based cryptosystems for embedded platforms,” J. Cryptograph. Eng., vol. 4, no. 2, pp. 123-134, 2014.

P. Farkaš, “Two countermeasures against reaction attacks on LEDApkc and other QC-MDPC and QC-LDPC based McEliece cryptosystems in ARQ setting heuristic discussion,” Proceedings of the 2018 26th International Conference on Software, Telecommunications and Computer Networks (SoftCOM), Split, 2018, pp. 1-5.

I. von Maurich and T. Güneysu, “Lightweight code-based cryptography: QC-MDPC McEliece encryption on reconfigurable devices,” Proceedings of the 2014 Design, Automation & Test in Europe Conference & Exhibition (DATE), Dresden, 2014, pp. 1-6.

T. Eisenbarth, T. G̈uneysu, S. Heyse, and C. Paar, “MicroEliece: McEliece for embedded devices,” in CHES, ser. Lecture Notes in Computer Science, C. Clavier and K. Gaj, Eds., vol. 5747, Springer, 2009, pp. 49-64.

I. Gorbenko, A. Kuznetsov, M. Lutsenko and D. Ivanenko, “The research of modern stream ciphers,” Proceedings of the 2017 4th International Conference Problems of Infocommunications. Science and Technology (PIC S&T), Kharkov, 2017, pp. 207-210. DOI: 10.1109/INFOCOMMST.2017.8246381

E. Persichetti, “Compact McEliece Keys based on Quasi-Dyadic Srivastava codes,” J. Mathematical Cryptology, vol. 6, no. 2, pp. 149-169, 2012.

A. Andrushkevych, Y. Gorbenko, O. Kuznetsov, R. Oliynykov, M. A. Rodinko, “Prospective lightweight block cipher for green IT engineering,” in: Kharchenko V., Kondratenko Y., Kacprzyk J. (eds), Green IT Engineering: Social, Business and Industrial Applications. Studies in Systems, Decision and Control, vol 171, Springer, Cham, 2019, pp. 95-112.

R. Misoczki, J.-P. Tillich, N. Sendrier, and P. S. L. M. Barreto, “MDPCMcEliece: New McEliece variants from moderate density parity-check codes,” Proceedings of the IEEE International Symposium on Information Theory (ISIT’2013), 2013, pp. 2069-2073.

I. Gorbenko, O. Kuznetsov, Y. Gorbenko, A. Alekseychuk and V. Tymchenko, “Strumok keystream generator,” Proceedings of the 2018 IEEE 9th International Conference on Dependable Systems, Services and Technologies (DESSERT), Kyiv, Ukraine, 2018, pp. 294-299.

S. Heyse, I. von Maurich, and T. G̈uneysu, “Smaller keys for code-based cryptography: QC-MDPC McEliece implementations on embedded devices,” in CHES, ser. Lecture Notes in Computer Science, G. Bertoni and J.-S. Coron, Eds., vol. 8086. Springer, 2013, pp. 273-292.

C. Chen, T. Eisenbarth, I. von Maurich, R. Steinwandt, “Differential power analysis of a McEliece cryptosystem,” Proceedings of the 13th Int. Conf. Appl. Cryptogr. Netw. Secur. (ACNS), June 2015, pp. 1-19.

Downloads

Published

2019-12-31

How to Cite

Gorbenko, Y., Kiian, A., Pushkar’ov, A., Korneiko, O., Smirnov, S., & Kuznetsova, T. (2019). CODE-BASED HYBRID CRYPTOSYSTEM: COMPARATIVE STUDIES AND ANALYSIS OF EFFICIENCY. International Journal of Computing, 18(4), 372-380. https://doi.org/10.47839/ijc.18.4.1608

Issue

Section

Articles