Expanding graphs of the Extremal Graph Theory and expanded platforms of post quantum cryptography

• Autorzy: Ustimenko Vasyl , Romańczuk-Polubiec Urszula , Wróblewska Aneta

Identyfikatory

DOI

10.15439/2019F343

• Konferencja: Federated Conference on Computer Science and Information Systems (14 ; 01-04.09.2019 ; Leipzig, Germany)
• Języki publikacji: EN

Abstrakty

EN

Explicit constructions in Extremal Graph Theory give appropriate lower bounds for Turan type problems. In the case of prohibited cycles, the explicit constructions can be used for various problems of Information Security. We observe recent applications of algebraic constructions of regular graphs of large girth and graphs with large cycle indicator to Coding Theory and Cryptography. In particular, we present a new multivariate platforms of postquantum Non-commutative Cryptography defined in graph theoretical terms.

Słowa kluczowe

EN

graphs of large girth; graphs of large cycle; indicator; graph based stream ciphers; multivariate cryptography; non-commutative cryptography

PL

wykres; graf; wskaźnik; szyfr strumieniowy; kryptografia

• Wydawca: Polskie Towarzystwo Informatyczne
• Czasopismo: Annals of Computer Science and Information Systems
• Rocznik: 2019
• Tom: Vol. 19
• Strony: 41--46
• Opis fizyczny: Bibliogr. 46 poz., wz.

Twórcy

autor

Ustimenko Vasyl

• Maria Curie-Skłodowska University, pl. Marii Curie-Skłodowskiej 1 20-031 Lublin, Poland

autor

Romańczuk-Polubiec Urszula

autor

Wróblewska Aneta

• Maria Curie-Skłodowska University, pl. Marii Curie-Skłodowskiej 1 20-031 Lublin, Poland

Bibliografia

• 1. B. Bollobas, Extremal graph theory, Academic Press, London, 1978.
• 2. M. Polak, U. Romańczuk, V. Ustimenko and A. Wróblewska, “On the applications of Extremal Graph Theory to Coding Theory and Cryptography”, Electronic Notes in Discrete Mathema Discrete Mathematics, N 43, 2013, p. 329-342. http://dx.doi.org/10.1016/j.endm.2013.07.051
• 3. F. Lazebnik, V. Ustimenko and A. J.Woldar, “A new series of dense graphs of high girth”, Bulletin of the American Mathematical Society (N.S.) 32, no. 1, 1995, pp. 73-79
• 4. V. Ustimenko, “On extremal graph theory and symbolic computations”, Dopovidi National Academy of Sciences of Ukraine, , N2, 2013, pp. 42-49.
• 5. V. Ustimenko, U. Romańczuk-Polubiec, A. Wróblewska, M. Polak and E. Zhupa, “On the implementation of new symmetric ciphers based on non-bijective multivariate maps”, Proceedings of the 2018 Federated Conference on Computer Science and Information Systems, M.Ganzha, L. Maciaszek, M. Paprzycki (eds). ACSIS, Vol. 15, 2018, pp. 397-405 http://dx.doi.org/http://dx.doi.org/10.15439/2018F204
• 6. V. Ustimenko, U. Romańczuk-Polubiec, A. Wróblewska, M. Polak and E. Zhupa, “On the constructions of new symmetric ciphers based on non-bijective multivariate maps of prescribed degree”, Security and Communication Networks, Volume 2019, Article ID 2137561, 15 pages. http://dx.doi.org/10.1155/2019/2137561
• 7. M. Klisowski and V. Ustimenko, “Graph based cubical multivariate maps and their crypto-graphical applications”, Advances on Superelliptic curves and their Applications, IOS Press, NATO Science for Peace and Security series -D: Information and Communication Security, vol 41, 2014, pp. 305 -327.
• 8. U. Romańczuk-Polubiec and V. Ustimenko, “On Multivariate Cryptosystems Based on Polynomially Compressed Maps with Invertible Decompositions”, Cryptography and Security Systems, Third International Conference, CSS 2014, Lublin, Poland, September 22-24, 2014. Proceedings, Communications in Computer and Information Science, 448, 2014, pp. 23-37. http://dx.doi.org/10.1007/978-3-662-44893-9_3
• 9. U. Romańczuk-Polubiec and V. Ustimenko, “On two windows multi-variate cryptosystem depending on random parameters”, Algebra and Discrete Mathematics, Volume 19, Number 1, 2015, pp. 101-129.
• 10. U. Romańczuk and V. Ustimenko, “On Families of Graphs of Large Cycle Indicator, Matrices of Large Order and Key Exchange Protocols With Nonlinear Polynomial Maps of Small Degree”, Mathematics in Computer Science, June 2012, Volume 6, Issue 2, pp 167-180, http://dx.doi.org/10.1007/s11786-012-0115-8
• 11. U. Romańczuk-Polubiec and V. Ustimenko, “On new key exchange multivariate protocols based on pseudorandom walks on incidence structures”, Dopovidi National Academy of Sciences of Ukraine, No. 1, 2015, pp 41-49. http://dx.doi.org/10.15407/dopovidi2015.01.041
• 12. V. Ustimenko, “On algebraic graph theory and non-bijective maps in cryptography”, Algebra and Discrete Mathematics, Volume 20, Number 1, 2015, pp. 152-170.
• 13. V. Ustimenko, “Explicit constructions of extremal graphs and new multivariate cryptosystems”, Studia Scientarium Mathematicarium Hungarica (Proceedings of Central. European Conference on Cryptology 2014, Budapest), vol 52, issue 2, June 2015, pp 185-204. http://dx.doi.org/ 10.1556/012.2015.52.2.1312
• 14. V. Ustimenko, “On the families of stable transformations of large order and their crypto-graphical applications”, Tatra Mt. Math. Publ., 70, 2017, pp. 107-117. http://dx.doi.org/10.1515/tmmp-2017-0021
• 15. V. Ustimenko, “On new symbolic key exchange protocols and cryptosystems based on hidden tame homomorphism”, Dopovidi National Academy of Sciences of Ukraine, N. 10, 2018, pp. 26-36. http://dx.doi.org/10.15407/dopovidi2018.10.026
• 16. V. Ustimenko and M. Klisowski, “On Noncommutative Cryptography with cubical multiva-riate maps of predictable density”, Proceedings of “Computing 2019” conference, London, 16-17, July, In: Arai K., Bhatia R., Kapoor S. (eds) Intelligent Computing. CompCom 2019. Advances in Intelligent Systems and Computing, vol 998. Springer, Cham. pp. 654-674. http://dx.doi.org/10.1007/978-3-030-22868-2_47
• 17. A. G. Myasnikov, V. Shpilrain and Alexander Ushakov, Non-commutative Cryptography and Complexity of Group-theoretic Problems, Mathematical Surveys and Monographs, American Mathematical Society, Volume 177, 2011. http://dx.doi.org/http://dx.doi.org/10.1090/surv/177
• 18. P.L.K. Priyadarsini, “A Survey on some Applications of Graph Theory in Cryptography”, Journal of Discrete Mathematical Sciences and Cryptography, 18:3, 2015, pp. 209-217. http://dx.doi.org/10.1080/ 09720529.2013.878819
• 19. V. Ustimenko, “On semigroups of multiplicative Cremona transformations and new solutions of Post Quantum Cryptography”, Cryptology ePrint Archive, 133, 2019.
• 20. O.S. Pustovit and V.O Ustimenko, “A new stream algorithms generating sensetive digests of digital documents”, Mathematical modelling in economics (to appear).
• 21. V. Ustimenko, “On desynchronised multivariate algorithms of El Gamal type for stable semigroups of affine Cremona group”, Theoretical and Applied Cybersecurity, section: theoretical and cryptographic problems of cybersecurity , NTTU KPI, Kyiv, Vol. 1, No. 1, 2019, pp. 22-30.
• 22. D. N. Moldovyan and N. A. Moldovyan, “A New Hard Problem over Non-commutative Finite Groups for Cryptographic Protocols”, International Conference on Mathematical Methods, Models, and Architectures for Computer Network Security, MMM-ACNS 2010: Computer Network Security pp. 183-194. http://dx.doi.org/10.1007/978-3-642-14706-7_14
• 23. L. Sakalauskas and P. Tvarijonas, “A. Raulynaitis, Key Agreement Protocol (KAP) Using Conjugacy and Discrete Logarithm Problema in Group Representation Level”, INFORMATICA, 2007, Vol. 18, No. 1, pp. 115-124
• 24. V. Shpilrain and A. Ushakov, “The conjugacy search problem in public key cryptography: unnecessary and insufficient”, Applicable Algebra in Engineering, Communication and Computing, August 2006, Volume 17, Issue 3-4, pp. 285-289. http://dx.doi.org/10.1007/s00200-006-0009-6
• 25. D. Kahrobaei and B. Khan, “A non-commutative generalization of ElGamal key exchange using polycyclic groups”, In IEEE GLOBECOM 2006 - 2006 Global Telecommunications Conference [4150920]. http://dx.doi.org/10.1109/GLOCOM.2006.290
• 26. A. Myasnikov, V. Shpilrain and A. Ushakov, Group-based Cryptography, Advanced Courses in Mathematics - CRM Barcelona, Birkhäuser Basel, XV, p. 183, 2008. http://dx.doi.org/10.1007/978-3-7643-8827-0
• 27. Zhenfu Cao, “New Directions of Modern Cryptography”, Boca Raton: CRC Press, Taylor & Francis Group, 2012, ISBN 978-1-4665-0140-9.
• 28. B. Fine, et. al. “Aspects of Non abelian Group Based Cryptography: A Survey and Open Problems”. ArXiv:1103.4093.
• 29. I. Anshel, M. Anshel, D. Goldfeld, “An algebraic method for public-key cryptography”, Mathematical Research Letters, 1999, 6(3-4), pp. 287-291.
• 30. S. R. Blackburn and S. D. Galbraith, “Cryptanalysis of two cryptosystems based on group actions”, In: Advances in Cryptology-ASIACRYPT ’99. Lecture Notes in Computer Science, Springer, Berlin, 1999, vol. 1716, pp. 52-61.
• 31. C. Ko, K.H., Lee, S.J., Cheon, J.H., Han, J.W., Kang, J.S. and Park, C., “New public-key cryptosystem using braid groups”, In: Advances in Cryptology-CRYPTO 2000, Santa Barbara, CA. Lecture Notes in Computer Science, Springer, Berlin, 2000, vol. 1880, pp. 166-83. http://dx.doi.org/10.1007/3-540-44598-6_10
• 32. G. Maze, C. Monico, J. Rosenthal, “Public key cryptography based on semigroup actions”, Advances in Mathematics of Communications, 2007, 1(4), pp. 489-507. http://dx.doi.org/10.3934/amc.2007.1.489
• 33. P. H. Kropholler, S.J. Pride , W.A.M. Othman K.B. Wong and P.C. Wong, “Properties of certain semigroups and their potential as platforms for cryptosystems”, Semigroup Forum, 2010, Vol. 81, pp. 172-186. http://dx.doi.org/10.1007/s00233-010-9248-8
• 34. J. A. Lopez Ramos, J. Rosenthal, D. Schipani and R. Schnyder, “Group key management based on semigroup actions”, Journal of Algebra and its applications, vol.16, No. 8, 2017. http://dx.doi.org/10.1142/S0219498817501481
• 35. G. Kumar and H. Saini, “Novel Noncommutative Cryptography Scheme Using Extra Special Group”, Security and Communication Networks ,Volume 2017, Article ID 9036382, 21 pages. doi: 10. 1155/2017/9036382
• 36. J. Ding., J. E. Gower and D. S. Schmidt, Multivariate Public Key Cryptosystems, Advances in Information Security, Springer, p. 260 v. 25, 2006. http://dx.doi.org/10.1007/978-0-387-36946-4
• 37. N. Koblitz, Algebraic aspects of cryptography, Springer, Berlin, Heidelberg, 1998. http://dx.doi.org/10.1007/978-3-662-03642-6
• 38. L. Goubin, J.Patarin, Bo-Yin Yang, Multivariate Cryptography, In: van Tilborg H.C.A., Jajodia S. (eds) Encyclopedia of Cryptography and Security. Springer, Boston, MA, (2nd Ed.), 2011, pp. 824-828. http://dx.doi.org/10.1007/978-1-4419-5906-5
• 39. R. Wagner, M. R. Magyarik, “A Public-Key Cryptosystem Based on the Word N Problem”, Advances in Cryptology, Proceedings of CRYPTO ’84, Santa Barbara, California, USA, August 19-22, 1984. http://dx.doi.org/10.1007/3-540-39568-7_3
• 40. V. Ustimenko, “On new multivariate cryptosystems based on hidden Eulerian equations”, Reports of Nath Acad of Sci, Ukraine, 2017. No. 5, pp 17-24. http://dx.doi.org/10.15407/dopovidi2017.05.017
• 41. V. Ustimenko, “On new multivariate cryptosystems based on hidden Eulerian equations over finite fields”, Cryptology ePrint Archive, 093, 2017. 111
• 42. V. Ustimenko and M. Klisowski, “On Noncommutative Cryptography and homomorphism of stable cubical multivariate transformation groups of infinite dimensional affine spaces”, Cryptology ePrint Archive, 593, 2019.
• 43. V. Ustimenko, “Maximality of affine group, hidden graph cryptosystem and graph’s stream ciphers”, Journal of Algebra and Discrete Mathematics, 2004, v.10, pp. 51-65.
• 44. V. Ustimenko, “Linguistic Dynamical Systems, Graphs of Large Girth and Cryptography”, Journal of Mathematical Sciences, Springer, Vol.140, N3, 2007, pp. 412-434. http://dx.doi.org/10.1007/s10958-007-0453-2
• 45. V. Ustimenko, “Graphs with Special Arcs and Cryptography”, Acta Applicandae Mathematica, November 2002, Volume 74, Issue 2, pp. 117-153 http://dx.doi.org/10.1023/A:1020686216463
• 46. A. Lubotzky, R. Phillips and P. Sarnak, “Ramanujan graphs”, Combinatorica, September 1988, Volume 8, Issue 3, pp. 261-277, http://dx.doi.org/10.1007/BF02126799

Uwagi

1. Track 2: Computer Science & Systems

2. Technical Session: 6th International Conference on Cryptography and Security Systems

3. Opracowanie rekordu ze środków MNiSW, umowa Nr 461252 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2020).