Logo PTI
Polish Information Processing Society
Logo FedCSIS

Annals of Computer Science and Information Systems, Volume 19

Position Papers of the 2019 Federated Conference on Computer Science and Information Systems

Expanding graphs of the Extremal Graph Theory and expanded platforms of Post Quantum Cryptography

, ,

DOI: http://dx.doi.org/10.15439/2019F343

Citation: Position Papers of the 2019 Federated Conference on Computer Science and Information Systems, M. Ganzha, L. Maciaszek, M. Paprzycki (eds). ACSIS, Vol. 19, pages 41–46 ()

Full text

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

References

  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