Post-Quantum Cryptography: generalized ElGamal cipher over GF(2518)

• Autorzy: Hecht P.

Identyfikatory

DOI

10.20904/284001

• Języki publikacji: EN

Abstrakty

EN

Post-Quantum Cryptography (PQC) attempts to find cryptographic protocols resistant to attacks by means of for instance Shor's polynomial time algorithm for numerical field problems like integer factorization (IFP) or the discrete logarithm (DLP). Other aspects are the backdoors discovered in deterministic random generators or recent advances in solving some instances of DLP. The use of alternative algebraic structures like non-commutative or non-associative partial groupoids, magmas, monoids, semigroups, quasigroups or groups, are valid choices for these new kinds of protocols. In this paper, we focus in an asymmetric cipher based on a generalized ElGamal non-arbitrated protocol using a non-commutative general linear group. The developed protocol forces a hard subgroup membership search problem into a non-commutative structure. The protocol involves at first a generalized Diffie-Hellman key interchange and further on the private and public parameters are recursively updated each time a new cipher session is launched. Security is based on a hard variation of the Generalized Symmetric Decomposition Problem (GSDP). Working with GF(2518) a 64-bits security is achieved, and if GF(25116) is chosen, the security rises to 127-bits. An appealing feature is that there is no need for big number libraries as all arithmetic if performed in Z251 and therefore the new protocol is particularly useful for computational platforms with very limited capabilities like smartphones or smartcards.

Słowa kluczowe

EN

post-quantum cryptography; non-commutative cryptography; finite fields

• Wydawca: Instytut Informatyki Teoretycznej i Stosowanej Polskiej Akademii Nauk
• Czasopismo: Theoretical and Applied Informatics
• Rocznik: 2016
• Tom: Vol. 28, No. 4
• Strony: 1--14
• Opis fizyczny: Bibliogr. 40 poz., rys.

Twórcy

autor

Hecht P.

• Maestrĭa en Seguridad Informătica Facultad de Ciencias Econ_omicas, Facultad de Ciencias Exactas y Naturales y Facultad de Ingenierĭa Universidad de Buenos Aires Av. Córdoba 2122, (C1120AAQ) Ciudad de Buenos Aires, Repŭblica Argentina

Bibliografia

• [1] L. Chen, S. Jordan, Y.-K. Liu, D. Moody, R. Peralta, R. Perlner, and D. Smith-Tone. Report on Post-Quantum Cryptography. Technical report, 2016. DOI: 10.6028/nist.ir.8105.
• [2] D. Moody. Update on the NIST Post-Quantum Cryptography Project, 2016. http://csrc. nist.gov/groups/SMA/ispab/, Accessed: 10.02.2017.
• [3] YB. Zhou and DG. Feng. Side-Channel Attacks: Ten Years After Its Publication and the Impacts on Cryptographic Module Security Testing. State Key Laboratory of Information Security, Institute of Software, Chinese Academy of Sciences, 2006.
• [4] B. Schneier. Did NSA put a secret backdoor in new encryption standard? https://www.wired.com/2007/11/securitymatters-1115/, Accessed: 10.02.2017.
• [5] R. Barbulescu, P. Gaudry, A. Joux, and E. Thom e. A Heuristic Quasi-Polynomial Algorithm for Discrete Logarithm in Finite Fields of Small Characteristic, pages 1-16. Springer Berlin Heidelberg, 2014. DOI: 10.1007/978-3-642-55220-5 1.
• [6] A. J. Menezes, P. C. Van Oorschot, and S. A. Vanstone. Handbook of applied cryptography. CRC press, 1996.
• [7] P. W. Shor. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Review, 41(2):303-332, 1999. DOI: 10.1137/S0036144598347011.
• [8] P. S. L. M. Barreto, F. P. Biasi, R. Dahab, J. C esar, G. C. C. F. Pereira, and J. E. Ricardini. Introdućăo ā criptografia pós-quăntica. Minicursos do XIII Simp osio Brasileiro em Seguranca da Informacăo e de Sistemas Computacionais--SBSeg, 2013.
• [9] L. Gerritzen, D. Goldfeld, M. Kreuzer, G. Rosenberger, and Shpilrain V. Algebraic Methods in Cryptography, volume 518. American Mathematical Soc., 2006.
• [10] B. Tsaban. Polynomial-time solutions of computational problems in noncommutativealgebraic cryptography. Journal of Cryptology, 28(3):601-622, 2015. DOI: 10.1007/s00145-013-9170-9.
• [11] A. Kalka. Non-associative public-key cryptography. arXiv:1210.8270, 2012.
• [12] Cz. Kościelny. Generating quasigroups for cryptographic applications. International Journal of Applied Mathematics and Computer Science, 12(4):559-569, 2002.
• [13] S. Markovski. Design of crypto primitives based on quasigroups. Quasigroups and Related Systems, 23(1):41-90, 2015.
• [14] D. Grigoriev and I. Ponomarenko. Constructions in public-key cryptography over matrix groups. In International Workshop on Algebraic Methods in Cryptography, volume 418 of Contemporary Mathematics, pages 103-119. American Mathematical Soc., 2005.
• [15] Z. Cao, X. Dong, and L. Wang. New public key cryptosystems using polynomials over non-commutative rings. IACR Cryptology ePrint Archive, 2007.
• [16] S.-H. Paeng, D. Kwon, K.-Ch. Ha, and J. H. Kim. Improved public key cryptosystem using finite non abelian groups. 2001.
• [17] J.-C. Birget, S. S. Magliverasy, and M. Sramkay. On public-key cryptosystems based on combinatorial group theory. Tatra Mt. Math. Publ, 33(137):137-148, 2006.
• [18] M. I. Gonzălez Vasco, C. Martĭnez, and R. Steinwandt. Towards a uniform description of several group based cryptographic primitives. Designs, Codes and Cryptography, 33(3):215-226, 2004.
• [19] V. Shpilrain and A. Ushakov. Thompson's Group and Public Key Cryptography, pages 151-163. Springer Berlin Heidelberg, 2005. DOI: 10.1007/11496137 11.
• [20] K. Mahlburg. An overview of braid group cryptography. 2004. http://www.math.wisc. edu/~boston/mahlburg.pdf.
• [21] E. K. Lee. Braid groups in cryptology. IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences, 87(5):986-992, 2004.
• [22] B. Eick and D. Kahrobaei. Polycyclic groups: A new platform for cryptology?arXiv:math/0411077, 2004.
• [23] A. Mahalanobis. The Die-Hellman key exchange protocol and non-abelian nilpotent groups. Israel Journal of Mathematics, 165(1):161-187, 2008. DOI: 10.1007/s11856-008-1008-z.
• [24] V. A. Shcherbacov. Quasigroups in cryptology. Computer Science Journal of Moldova, 17(2):50, 2009. https://ibn.idsi.md/en/vizualizare_articol/2712.
• [25] S. S. Magliveras, D. R. Stinson, and T. van Trung. New approaches to designing public key cryptosystems using one-way functions and trapdoors infinite groups. Journal of Cryptology,15(4):285-297, 2002.
• [26] V. Shpilrain and G. Zapata. Combinatorial group theory and public key cryptography. Applicable Algebra in Engineering, Communication and Computing, 17(3):291-302, 2006. DOI: 10.1007/s00200-006-0006-9.
• [27] J. P. Hecht. Un modelo compacto de criptografia asimetrica empleando anillos no conmutativos. In Actas del V Congreso Iberoamericano de Seguridad Informatica CIBSI, volume 9, pages 188-201, 2009.
• [28] P. Hecht. A Zero-Knowledge authentication protocol using non commutative groups. In Actas del VI Congreso Iberoamericano de Seguridad Informatica CIBSI, volume 11, pages 96-102, 2011.
• [29] P. Hecht. Criptografia no conmutativa usando un grupo general lineal de orden primo de mersenne. In Actas del VII Congreso Iberoamericano de Seguridad Informatica CIBSI, volume 13, pages 147-153, 2013.
• [30] P. Hecht. A post-quantum set of compact asymmetric protocols using a general linear group. In Actas del VIII Congreso Iberoamericano de Seguridad Informatica CIBSI, volume 15, pages 96-101, 2015.
• [31] P. Hecht. Zero-knowledge proof authentication using Left Self Distributive Systems: a postquantum approach. In Actas del VIII Congreso Iberoamericano de Seguridad Informatica CIBSI, volume 15, pages 96-101, 2015.
• [32] J. Kamlofsky, J. Hecht, S. Abdel Masih, and O. Hidalgo Izzi. A Diffie-Hellman compact model over non-commutative rings using quaternions. In VIII Congreso Iberoamericano de Seguridad Informatica CIBSI, Quito, 2015.
• [33] R. Lidl and H. Niederreiter. Finite fields, volume 20. Cambridge university press, 1997.
• [34] T. Beth, D. Jungnickel, and H. Lenz. Encyclopedia of Mathematics and Its Applications, volume 69. Cambridge University Press, Cambridge, 1999.
• [35] R. A. Horn and Ch. R. Johnson. Matrix analysis. Cambridge university press, 2012.
• [36] J. Overbey, W. Traves, and J. Wojdylo. On the key space of the Hill Cipher. Cryptologia, 29(1):59-72, 2005. DOI: 10.1080/0161-110591893771.
• [37] A. W. Dent. Fundamental problems in provable security and cryptography. Philosophical Transactions of the Royal Society of London A: Mathematical, Physical and Engineering Sciences, 364(1849):3215-3230, 2006. DOI: 10.1098/rsta.2006.1895.
• [38] A. D. Myasnikov and A. Ushakov. Cryptanalysis of matrix conjugation schemes. Journal of Mathematical Cryptology, 8(2), 2014. DOI: 10.1515/jmc-2012-0033.
• [39] A. A. Kamal and A. M. Youssef. Cryptanalysis of Alvarez et al. key exchange scheme. Information Sciences, 223:317-321, 2013. DOI: 10.1016/j.ins.2012.10.010.
• [40] J. Katz and Y. Lindell. Introduction to modern cryptography: principles and protocols. Cryptography and network security, 2008.

Uwagi

PL

Opracowanie ze środków MNiSW w ramach umowy 812/P-DUN/2016 na działalność upowszechniającą naukę (zadania 2017).