Logo PTI Logo FedCSIS

Proceedings of the 18th Conference on Computer Science and Intelligence Systems

Annals of Computer Science and Information Systems, Volume 35

On Extremal Algebraic Graphs and implementations of new cubic Multivariate Public Keys

, ,

DOI: http://dx.doi.org/10.15439/2023F7763

Citation: Proceedings of the 18th Conference on Computer Science and Intelligence Systems, M. Ganzha, L. Maciaszek, M. Paprzycki, D. ÅšlÄ™zak (eds). ACSIS, Vol. 35, pages 1179–1184 ()

Full text

Abstract. Algebraic Constructions of Extremal Graph Theory were efficiently used for the construction of Low Density Parity Check Codes for satellite communication, constructions of stream ciphers and Postquantum Protocols of Noncommutative cryptography and corresponding El Gamal type cryptosystems. We shortly observe some results in these applications and present idea of the usage of algebraic graphs for the development of Multivariate Public Keys (MPK). Some MPK schemes are presented at theoretical level, implementation of one of them is discussed.

References

  1. F. Lazebnik, V.Ustimenko, Some Algebraic Constructions of Dense Graphs of Large Girth and of Large Size, DIMACS series in Discrete Mathematics and Theoretical Computer Science , v.10, (1993) 75 93.
  2. F. Lazebnik, V.Ustimenko, Some Algebraic Constractions of Dense Graphs of Large Girth and ofLarge Size, DIMACS series in Discrete Mathematics and Theoretical Computer Science , v.10, (1993) 75 - 93.
  3. F.Lazebnik V. Ustimenko and A.J.Woldar, A new series of dense graphs of high girth, Bulletin of the AMS 32 (1) (1995), 73-79.
  4. V. Ustimenko, Coordinatisation of Trees and their Quotients, in the Voronoj’s Impact on Modern Science, Kiev, Institute of Mathematics, 1998, vol. 2, 125-152.
  5. V. Ustimenko, Linguistic Dynamical Systems, Graphs of Large Girth and Cryptography, Journal of Mathematical Sciences.- Springer.- vol.140.- N3 .- 2007 .- P. 412-434.
  6. V. . Ustimenko On the extremal graph theory and symbolic compu- tations, Dopovidi National Academy of Sci, Ukraine, 2013, No. 2, p. 42-49.
  7. V. Ustimenko, CRYPTIM: Graphs as Tools for Symmetric Encryption, Lecture Notes in Computer Science, Springer, LNCS 2227, Proceedings of AAECC-14 Symposium on Applied Algebra, Algebraic Algorithms and Error Correction Codes, November 2001, pp. 278-286.
  8. V. Ustimenko, U. Romanczuk-Polubiec, A. Wroblewska, M. Polak, 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 213756.
  9. Alexei G. Myasnikov, Vladimir Shpilrain, Alexander Ushakov. Non-commutative Cryptography and Complexity of Group-theoretic Problems. American Mathematical Society, 2011.
  10. A. G. Myasnikov, A. Roman’kov, A linear decomposition attack, Groups Complex. Cryptol. 7, No. 1 (2015), 81-94.
  11. V. A. Roman’kov, A nonlinear decomposition attack, Groups Complex. Cryptol. 8, No. 2 (2016), 197-207.
  12. V. Roman’kov, An improved version of the AAG cryptographic protocol, Groups, Complex., Cryptol, 11, No. 1 (2019), 35-42.
  13. A. Ben-Zvi, A. Kalka and B. Tsaban, Cryptanalysis via algebraic span, In: Shacham H. and Boldyreva A. (eds.) Advances in Cryptology - CRYPTO 2018 - 38th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 19-23, 2018, Proceedings, Part I, Vol. 10991, 255-274, Springer, Cham (2018).
  14. B. Tsaban, Polynomial-time solutions of computational problems in noncommutative-algebraic cryptography, J. Cryptol. 28, No. 3 (2015), 601-622.
  15. B. Bollobas, Extremal Graph Theory, Academic Press 1978, Dover, 2004.
  16. Tymoteusz Chojecki, Vasyl Ustimenko, On fast computations of numerical parameters of homogeneous algebraic graphs of large girth and small diameter and encryption of large files, IACR e-print archive, 2022/908.
  17. Vasyl Ustimenko, On Extremal Algebraic Graphs and Multivariate Cryptosystems IACR e-print archive, 2022/1537.
  18. Vasyl Ustimenko, On the families of algebraic graphs with the fastest growth of cycle indicator and their applications, IACR e-print archive, 022/1668(PDF)
  19. V. Ustimenko, Graphs in terms of Algebraic Geometry, symbolic computations and secure communications in Post-Quantum world, UMCS Editorial House, Lublin, 2022, 198 p.
  20. Anne Canteaut, Franois-Xavier Standaert (Eds.), Eurocrypt 2021, LNCS 12696, 40th Annual International Conference on the Theory and Applications of Cryptographic Techniques Zagreb, Croatia, October 1721, 2021, Proceedings, Part I, Springer, 2021, 839p.
  21. O. Zariski, P. Samuel, Commutative algebra, 2, Springer (1975).
  22. I.R. Shafarevich, Basic algebraic geometry, Springer (1977) (Translated from Russian).
  23. R. Hartshorne, Algebraic geometry, Springer (1977).
  24. V. Ustimenko, On new results on Extremal Graph Theory, Theory of Algebraic Graphs and their applications in Cryptography and Coding The ory, Reports of Nath. Acad. of Sci. of Ukraine, 2022, No. 4, P. 42-49.
  25. J. Ding, J. E. Gower, D. S. Schmidt, Multivariate Public Key Cryptosystems, 260. Springer, Advances in Information Security, v. 25, (2006).
  26. N. Koblitz, Algebraic aspects of cryptography, Springer (1998), 206 P.
  27. L. Goubin, J.Patarin, Bo-Yin Yang, Multivariate Cryptography, Encyclopedia of Cryptography and Security, (2nd Ed.) 2011, 824-828.
  28. https://csrc.nist.gov/pubs/pd/2021/08/04/migration−to−postquantum−cryptography/final
  29. M. Noether, Luigi Cremona, Mathematische Annalen, 59 (1904), pp. 1-19.
  30. Lazebnik, F., Ustimenko, V.A. and A.J. Woldar, A characterisation of the components of the graph D(k, q), Discrete Mathematics, 157 (1996), pp. 271-283.
  31. V. A. Ustimenko, T. Chojecki, M. Klisowski, On Extremal Algebraic Graphs and implementations of new cubic Multivariate Public Keys, https://eprint.iacr.org/2023/744