Code-Based Public-Key Cryptosystems: the current state, the existing contradictions and prospects of practical use for the post-quantum period

Alexandr Kuznetsov V.N. Karazin Kharkiv National University
Andriy Pushkar’ov State Service of Special Communication and Information Protection of Ukraine
Sergii Kavun Department of Information Technologies, Kharkiv Educational and Research Institute of the University of Banking
Vyacheslav Kalashnikov Department of Systems and Industrial Engineering, Campus Monterrey

Keywords: Public-Key Cryptosystems, Post-Quantum Cryptography, Code-Based Cryptography

Abstract

Discusses the asymmetric cryptosystem based on algebraic coding, are investigated with temporary status, controversies and prospects of practical use for the post-quantum period. We propose a new scheme of crypto-transformation, significantly increases the relative rate of information transmission. Shown the advantage of the proposed design compared to the already known schemes Mac-Elisa and Niederreiter.

Downloads

Download data is not yet available.

Author Biographies

Alexandr Kuznetsov, V.N. Karazin Kharkiv National University

Doctor of Sciences (Engineering), Full Prof.

Andriy Pushkar’ov, State Service of Special Communication and Information Protection of Ukraine

Director of department

Sergii Kavun, Department of Information Technologies, Kharkiv Educational and Research Institute of the University of Banking

Doctor of Sciences (Economics), Ph.D. (Engineering), Full Prof.

Vyacheslav Kalashnikov, Department of Systems and Industrial Engineering, Campus Monterrey

Doctor of Sciences (Physics and Mathematics), Full Prof.

References

Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone. Handbook of Applied Cryptography – CRC Press, 1997. – 794 р.

Niels Ferguson and Bruce Schneier. Practical Cryptography. – John Wiley & Sons, 2003. – 432 pp.

Arto Salomaa. Public-Key Cryptography, Second, Enlarged Edition. – Springer-Verlag, Berlin, Heidelberg, New York, 1996. – x+271 pp.

Nigel Smart. Cryptography: An Introduction (3rd Edition). – 432 pp. https://www.cs.umd.edu/~waa/414-F11/IntroToCrypto.pdf

David Deutsch and Richard Jozsa. Rapid solutions of problems by quantum computation. // Proceedings of The Royal Society of London A: Mathematical, Physical and Engineering Sciences, vol. 439, no. 1907. – 1992. – Р. 553-558.

Cleve R., Ekert A., Macchiavello C., Mosca M. Quantum algorithms revisited // Proceedings of The Royal Society of London A: Mathematical, Physical and Engineering Sciences, vol. 454, no. 1969. – 1998. – P. 339-354.

Simon D. R. On the power of quantum computation // Foundations of Computer Science, 1994 Proceedings., 35th Annual Sym-posium. – P. 116-123.

Grover L. 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. – P. 212–219.

Grover L. A framework for fast quantum mechanical algorithms. // Proceedings of the 13th annual ACM symposium on theory of computing (STOC' 98). ACM Press, New York. – 1998. – P. 53–62.

Shor P. W. Algorithms for quantum computation: discrete logarithms and factoring // Foundations of Computer Science: Conference Publications. – 1994. – P. 124-134.

Shor P. W. Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer // Foundations of Computer Science: Conference Publications. – 1997. – P. 1484-1509.

Neal Koblitz and Alfred J. Menezes. A Riddle Wrapped in an Enigma. https://eprint.iacr.org/2015/1018.pdf.

Committee on National Security Systems, Use of public standards for the secure sharing of information among national security systems, Advisory Memorandum 02-15, July 2015. https://cryptome.org/2015/08/CNSS_Advisory_Memo_02-15.pdf.

Bernstein, Daniel J., Buchmann, Johannes, and Dahmen, Erik. Post-Quantum Cryptography. – 2009, Springer-Verlag, Berlin-Heidleberg. – 245 p.

McEliece R. J. A public-key cryptosystem based on algebraic coding theory. DSN Progress Report 42-44, Jet Propulsion Lab., Pasadena, CA, January-February, 1978. P. 114-116.

Niederreiter H. Knapsack-type cryptosystems and algebraic coding theory // Problem Control and Inform Theory, 1986, v. 15. P. 19-34.

T. R. N. Rao and K. H. Nam. Private-key algebraic-coded cryptosystem. Advances in Cryptology – CRYPTO 86, New York. – NY: Springer. – P. 35–48.

Yu. V. Stasev, A. A. Kuznetsov. Asymmetric Code-Theoretical Schemes Constructed with the Use of Algebraic Geometric Codes // Cybernetics and Systems Analysis, Volume 41, Issue 3, May 2005, P. 354–363.

Sidel'nikov V.M. Kriptografiya i teoriya kodirovaniya. Materialy konferentsii «Moskovskii universitet i razvitie kriptografii v Rossii», MGU. – 2002. – 22 s.

Sidel'nikov V.M., Shestakov S.O. O sisteme shifrovaniya, postroennoi na osnove obobshchennykh kodov Rida-Solomona. // Diskretnaya matematika. – 1992. – T.4.№3. – S. 57-63.

Kuznetsov A.A. Algebraicheskaya teoriya blokovykh kodov i ee prilozheniya v kriptografii // Persha mizhnarodni naukova konferencija 25–27 travnja 2005r. „Teorija ta metody obrobky sygnaliv”. Tezy dopovidej. – K.: NAU. – 2005. – S. 6-8.

Kuznetsov A.A. Issledovanie effektivnosti kriptosistem na algebraicheskikh blokovykh kodakh // Systemy obrobky informacii'. – Kharkiv: KhUPS. –2005 – Vyp. 4. – S. 202–206.

Kuznetsov A.A. Issledovanie pomekhoustoichivosti i kriptostoikosti teoretiko-kodovykh skhem. // Modeljuvannja ta informacijni tehnologii'. – Kyi'v: NANU. – 2005. – №33. – S. 81-84.

Fisher Jean-Dernard, Jacques Stern. An efficient Pseudo-Random Generator Provably as Secure as Syndrome Decoding / Jean-Dernard Fisher, Stern Jacques // EUROCRYPT’96 Proceeding, LNCS 1070. P. 245-255.

Kuznetsov A.A., Korolev R.V., Ryabukha Yu.N. Usovershenstvovannyi metod bystrogo formirovaniya posledovatel'nostei psevdosluchainykh chisel // Zbirnyk naukovyh prac' HUPS. – Kharkiv: KhUPS. – 2008. – Vyp. 3 (18). – S. 101-104.

Gaborit, P., Laudaroux, C., and Sendrier, N.: Synd: a very fast code-based cipher stream with a security reduction. In IEEE Conference, ISIT’07, pages 186–190.

Kirill Morozov, Tsuyoshi Takagi. Zero-Knowledge Protocols for the McEliece Encryption // Information Security and Privacy Volume 7372 of the series Lecture Notes in Computer Science pp 180-193.

Bernstein D. Post-quantum cryptography [Text] / D. Bernstein, J. Buchmann, E. Dahmen. – Berlin: Springer, 2009. – 246 p.

Courtois, N., Finiasz M., Sendrier N.: How to achieve a McEliece-based digital signature scheme. In Advances in Cryptology - ASIACRYPT 2001, volume 2248, pp. 157–174.

Finiasz M.: Parallel-CFS: Strengthening the CFS McEliece-based signature scheme. In Biryukov A., Gong G., Stinson D., eds.: Selected Areas in Cryptography. Volume 6544 of LNCS., Springer (2010) pp. 159-170.

Stern J.: A new identification scheme based on syndrome decoding. In Advances in Cryptology - CRYPTO’93, volume 773 of LNCS. Springer Verlag (1994).

Veron P.: Improved identification schemes based on error-correcting codes. Appl. Algebra Eng. Commun. Comput., 8(1):57–69 (1996).

Anne Canteaut and Nicolas Sendrier. Cryptanalysis of the original McEliece cryptosystem. In Kazuo Ohta and Dingyi Pei, editors, Advances in cryptology — ASIACRYPT’98, volume 1514 of Lecture Notes in Computer Science, pp. 187–199.

Vladimir M. Sidelnikov and Sergey O. Shestakov. On insecurity of cryptosystems based on generalized Reed-Solomon codes. Discrete Mathematics and Applications, 1992. pp. 439–444.

Minder L., Shokrollahi A. Cryptanalysis of the Sidelnikov Cryptosystem // Advances in Cryptology — EUROCRYPT 2007: 26th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Barcelona, Spain, May 20-24, 2007. Proceedings — Springer Berlin Heidelberg, 2007. — P. 347—360.

Daniel J. Bernstein and Tanja Lange and Christiane Peters. Attacking and defending the McEliece cryptosystem. https://cr.yp.to/codes/mceliece-20080807.pdf.

E. Berlekamp, R. McEliece, H. van Tilborg. On the Inherent Intractability of Certain Coding Problems. // IEEE Transactions on Information Theory, vol. IT-24, No. 3, May 1978. – Р. 384-386.

Clark G.C., Cain J.B. Error-Correction Coding for Digital Communications. – Springer, 1981, - 432 p.

Blahut R. E. Theory and Practice of Error Control Codes. – Addison Wesley Publishing Company, Inc., Reading, Massachusetts, 1983, 1983, – 500 pp.

F.J. MacWilliams and N.J.A. Sloane. The theory of error-correcting codes. – North-Holland, Amsterdam, New York, Oxford, 1977, – 762 pp.

Claude E. Shannon. Communication in the Presence of Noise. Proceedings of the IRE, vol. 37, no. 1, pp. 10–21, Jan. 1949.

V. D. Goppa. Novyi klass lineinykh korrektiruyushchikh kodov // Probl. peredachi inform., 1970, tom 6, Vyp. 3, S. 24–30.

V. D. Goppa. Na neprivodimykh kodakh dostigaetsya propusknaya sposobnost' DSK. // Probl. peredachi inform., 1974, tom 10, Vyp. 1, S. 111–112.

National Institute of Standards and Technology, “FIPS-197: Advanced Encryption Standard”, November 2001: http://csrc.nist.gov/publications/ fips/fips197/fips-197.pdf.

A New Encryption Standard of Ukraine: The Kalyna Block Cipher. https://eprint.iacr.org/2015/650.pdf.

Raphael Overbeck, Nicolas Sendrier, Code-based cryptography. In: Daniel J. Bernstein, et al. (eds). First International Workshop on Post-quantum Cryptography, PQ Crypto 2006, Leuven, The Netherland, May 23-26, 2006. Selected papers, pp. 95-145.

D. J. Bernstein. Grover vs. McEliece. In N. Sendrier, editor, Post-Quantum Cryptography, Third International Workshop, PQCrypto 2010, Darmstadt, Germany, May 25-28, 2010. Proceedings, volume 6061 of Lecture Notes in Computer Science, pages 73–80. Springer, 2010.

A. Menezes, P. van Oorschot, S. Vanstone. Chapter 14. Efficient Implementation // Handbook of Applied Cryptography. – CRC-Press, 1996. – 816 p.

Kerry Maletsky. RSA vs ECC Comparison for Embedded Systems. White Paper. Atmel Corporation – 2015, 5p. http://www.atmel.com/images/atmel-8951-cryptoauth-rsa-ecc-comparison-embedded-systems-whitepaper.pdf.

John Proos and Christof Zalka. Shor’s discrete logarithm quantum algorithm for elliptic curves. arxiv.quant-ph/0301141 v2, 2004.

Ziatdinov M. Using frequency analysis and Grover's algorithm to implement known ciphertext attack on symmetric ciphers // Lobachevskii Journal of Mathematics 2013 vol.34 N4, pages 313-315.

Metod nedvijkovogo rivnovagovogo koduvannja / V. B. Dudykevych, O. O. Kuznjecov, B. P. Tomashevs'kyj // Suchasnyj zahyst informacii'. - 2010. - № 3. - S. 57-68. - Rezhym dostupu: http://nbuv.gov.ua/UJRN/szi_2010_3_10.

Tietavainen A., Perko A. There are no unknown perfect binary codes. - Annales Universitatis Turkuensis. - Ser. A, I 148, 3-10[6], 1971.

Lint van J. H. Nonexistence theorems for perfect error-correcting codes. - Computers in Algebra and Number Theory. - Vol. IV [6], 1971.