Logo PTI Logo FedCSIS

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

Annals of Computer Science and Information Systems, Volume 35

Extremal algebraic graphs, quadratic multivariate public keys and temporal rules

,

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

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 1173–1178 ()

Full text

Abstract. We introduce large groups of quadratic transformations of a vector space over the finite fields defined via symbolic computations with the usage of algebraic constructions of Extremal Graph Theory. They can serve as platforms for the protocols of Noncommutative Cryptography with security based on the complexity of word decomposition problem in noncommutative polynomial transformation group. The modifications of these symbolic computations in the case of large fields of characteristic two allow us to define quadratic bijective multivariate public keys such that the inverses of public maps has a large polynomial degree. Another family of public keys is defined over arbitrary commutative ring with unity. We suggest the usage of constructed protocols for the private delivery of quadratic encryption maps instead of the public usage of these transformations, i.e. the idea of temporal multivariate rules with their periodical change.

References

  1. A. Canteaut and F. X. Standaert (Eds.), 40th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Eurocrypt 2021, LNCS 12696, Zagreb, Croatia, October 17–21, 2021, Proceedings, Part I, Springer, 2021, 839p, https://doi.org/10.1007/978-3-030-77886-6
  2. J. Ding, J. Deaton, , Vishakha, B.-Y. Yang, The nested subset differential attack a practical direct attack against LUOV which forges a signature within 210 minutes, Eurocrypt 2021, Part 1, pp. 329-347, https://doi.org/10.1007/978-3-030-77870-5_12
  3. W. Beullens, Improved cryptanalysis of UOV and Rainbow, Eurocrypt 2021, Part 1, pp. 348-373, https://doi.org/10.1007/978-3-030-77870-5_13
  4. L. Goubin, J. Patarin, B.-Y. Yang, Multivariate cryptography, Encyclopedia of Cryptography and Security (2nd Ed.) 2011, pp. 824-828, https://doi.org/10-.1007/978-1-4419-5906-5_421
  5. J. Ding, A. Petzolt and D. S. Schmidt, Multivariate public key cryptosystems, Springer, ADIS, vol. 80, 2020, https://doi.org/10.1007/978-1-0716-0987-3_2
  6. N. Koblitz, Algebraic aspects of cryptography, Springer, 1998, p. 206, https://doi.org/10.1007/978-3-662-03642-6_1
  7. V. Ustimenko, Linear codes of Schubert type and quadratic public keys of Multivariate Cryptography, IACR e-print archive, 2023/175, https://eprint.iacr.org/2023/175
  8. F.Lazebnik , V. Ustimenko and A.J.Woldar, A new series of dense graphs of high girth, Bulletin of the AMS 32 (1) (1995), pp. 73-79, https://doi.org/10.1090/s0273-0979-1995-00569-0
  9. V. Ustimenko, On the extremal graph theory and symbolic computations, Dopovidi National Academy of Sci, Ukraine, 2013, No. 2, pp. 42-49.
  10. V. Ustimenko, M. Klisowski, On Noncommutative Cryptography with cubical multivariate maps of predictable density, In “Intelligent Computing”, Proceedings of the 2019 Computing Conference, Volume 2, Part of Advances in Intelligent Systems and Computing(AISC), volume 99, pp. 654-674, https://doi.org/10.1007/978-3-030-22868-2_47
  11. V. Ustimenko, Graphs in terms of Algebraic Geometry, symbolic computations and secure communications in Post-Quantum world, University of Maria Curie Sklodowska Editorial House, Lublin, 2022, 198 p.
  12. A. G. Myasnikov, V. Shpilrain and A. Ushakov, Non-commutative cryptography and complexity of group-theoretic problems, American Mathematical Society, 2011, https://doi.org/10.1090/surv/177/05
  13. B. Tsaban, Polynomial-time solutions of computational problems in noncommutative-algebraic cryptography , J. Cryptol. 28, No. 3 (2015), pp. 601-622, https://doi.org/10.1007/s00145-013-9170-9
  14. V. Ustimenko, On new symbolic key exchange protocols and cryptosystems based on a hidden tame homomorphism, Dopovidi National Academy of Sci, Ukraine, 2018, n10, pp. 26-36, https://doi.org/10.15407/dopovidi2018.10.026
  15. V. Ustimenko and A. Wroblewska, Dynamical systems as the main instrument for the constructions of new quadratic families and their usage in cryptography, Annales UMCS Informatica AI XII, 3 (2012) pp. 65–74, https://doi.org/10.2478/v10065-012-0030-2
  16. V. A. Ustimenko, Graphs with special arcs and cryptography, Acta Applicandae Mathematicae, vol. 71, N2, November 2002, pp. 117-153, https://doi.org/10.1023/a:1020686216463
  17. 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, https://doi.org/10.1016/s0012-365x(96)83019-6
  18. V. Ustimenko, Linguistic dynamical systems, graphs of large girth and cryptography, Journal of Mathematical Sciences, Springer, vol.140, N3 (2007) pp. 461-471, https://doi.org/10.1007/s10958-007-0453-2
  19. Anshel, M. Anshel and D. Goldfeld, An algebraic method for public-key cryptography, Math. Res.Lett. 6(3–4), pp. 287–291 (1999), 169 https://doi.org/10.4310/mrl.1999.v6.n3.a3
  20. 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, vol. 1716, pp. 52–61. Springer, Berlin (1999), https://doi.org/10.1007/978-3-540-48000-6_6
  21. K.H. Ko, S.J. Lee, J.H. Cheon, J.W. Han, J.S. Kang and C. Park, New public-key cryptosystem using braid groups, In: Advances in Cryptology—CRYPTO 2000, Santa Barbara, CA. Lecture Notes in Computer Science, vol. 1880, pp. 166-183. Springer, Berlin (2000), https://doi.org/10.1007/3-540-44598-6_10
  22. G. Maze, C. Monico and J. Rosenthal, Public key cryptography based on semigroup actions, Adv.Math. Commun. 1(4), pp. 489–507 (2007), https://doi.org/10.3934/amc.2007.1.489
  23. 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) 81: pp. 172–186, https://doi.org/10.1007/s00233-010-9248-8
  24. J.A. Lopez Ramos, J. Rosenthal, D. Schipani and R. Schnyder, Group key management based on semigroup actions, Journal of Algebra and its applications, 2017, vol.16 (08):1750148, https://doi.org/10.1142/s0219498817501481
  25. G.Kumar and H. Saini, Novel noncommutative cryptography scheme using extra special group, Security and Communication Networks ,Volume 2017, Article ID 9036382, 21 pages, https://doi.org/10.1155/2017/9036382
  26. A. Wroblewska, Linguistic dynamical systems based on algebraic graphs and their application in cryptography, PhD Thesis, Institute of Fundamental Technological Research Polish Academy of Sciences, Warsaw, Poland, 2017, https://oldwww.ippt.pan.pl/_download/doktoraty/2016wroblewska_a_doktorat.pdf
  27. V. Ustimenko, A. Wroblewska, Extremal algebraic graphs, quadratic multivariate public keys and temporal rules, https://eprint.iacr.org/2023/738