Logo PTI Logo FedCSIS

Position and Communication Papers of the 16th Conference on Computer Science and Intelligence Systems

Annals of Computer Science and Information Systems, Volume 26

On computations with Double Schubert Automaton and stable maps of multivariate cryptography

DOI: http://dx.doi.org/10.15439/2021F67

Citation: Position and Communication Papers of the 16th Conference on Computer Science and Intelligence Systems, M. Ganzha, L. Maciaszek, M. Paprzycki, D. Ślęzak (eds). ACSIS, Vol. 26, pages 123–130 ()

Full text

Abstract. The families of bijective transformations $G\_n$ of affine space $K^n$ over general commutative ring $K$ of increasing order with the property of stability will be constructed. Stability means that maximal degree of  elements of  cyclic subgroup generated by the transformation of degree $d$ is bounded by $d$.  In the case $K=F\_q$ these transformations of  $K^n$ can be of an exponential order.  We introduce large groups formed by quadratic transformations and numerical encryption algorithm protected by secure protocol of Noncommutative Cryptography. The construction of transformations is presented in terms of walks on Double Schubert Graphs.

References

  1. J. Ding, J. E. Gower, D. S. Schmidt, Multivariate Public Key Cryptosystems. Springer, Advances in Information Security, V. 25, 2006.
  2. J. Porras, J. Baena, J. Ding New Candidates for Multivariate Trapdoor Functions, Revista Colombiana de Matematicas 49(1):57-76 (November 2015).
  3. V. A. Ustimenko, Explicit constructions of extremal graphs and new multivariate cryptosystems, Studia Scientiarum Mathematicarum Hungarica, Special issue “Proceedings of The Central European Conference, 2014, Budapest”, volume 52, issue 2, June 2015, pp. 185-204.
  4. V. Ustimenko, Linguistic Dynamical Systems, Graphs of Large Girth and Cryptography, Journal of Mathematical Sciences, Springer, vol.140, N3 (2007) pp. 412-434.
  5. A. Wróblewska, On some properties of graph based public keys, Albanian Journal of Mathematics, Volume 2, Number 3, 2008, 229-234, NATO Advanced Studies Institute: "New challenges in digital communications".
  6. V. Ustimenko, A. Wróblewska, On the key exchange with nonlinear polynomial maps of stable degree, Annalles UMCS Informatica AI XI, 2 (2011), 81-93.
  7. V Ustimenko, U. Romańczuk, On Dynamical Systems of Large Girth or Cycle Indicator and their applications to Multivariate Cryptography, in "Artificial Intelligence, Evolutionary Computing and Metaheuristics ", In the footsteps of Alan Turing Series: Studies in Computational Intelligence, Vol. 427, Springer, January , 2013, 257-285.
  8. V. Ustimenko, A. Wróblewska, Dynamical systems as the main instrument for the constructions of new quadratic families and their usage in cryptography, Annales UMCS Informatica AI, ISSN 1732-1360, vol. 12, N3 (2012), 65-74.
  9. M. Klisowski, Zwiększenie bezpieczeństwa kryptograficznych algorytmów wielu zmiennych bazujących na algebraicznej teorii grafów, PhD thesis, Częstochowa, 2014.
  10. M. Klisowski, V. Ustimenko, Graph based cubical multivariate maps and their cryptographical applications, in “ Advances on Superelliptic curves and their Applications”, IOS Press, NATO Science for Peace and Security series - D: Information and Communication Security, vol 41, 2015, pp. 305 -327.
  11. L. Babai, Graph Isomorphism in Quasipolinomial Time, arXive: 151203547v1 [cs. DS], 11 Dec 2015.
  12. V. Ustimenko, On Schubert cells in Grassmanians and new algorithms of multivariate cryptography, Proceedings of the Institite of Mathematics, Minsk, 2015, Volume 23, N 2, pp. 137-148 (Proceedings of international conference “Discrete Mathematics, algebra and their applications”, Minsk, Belarus, September 14-18, 2015, dedicated to the 100th anniversary of Dmitrii Alexeevich Suprunenko).
  13. A. Cossidente, M. J. de Ressmine, Remarks on Singer Cycle Groups and Their Normalizers, Designs, Codes and Cryptography, 32, 97-102, 2004.
  14. W. Kantor, Linear groups containing a Singer cycle, J. of Algebra 62, 1982, 232-234.
  15. V. A. Ustimenko, On the Families of Stable Multivariate Transformations of Large Order and Their Cryptographical Applications, Tatra Mountains Mathematical Publications,2O17, 70(1), pp 107-117.
  16. V. A. Ustimenko, On algebraic graph theory and non–bijective maps in cryptography, Algebra and Discrete Mathematics, Volume 20 (2015). Number 1, pp. 152-170.
  17. V. A. Ustimenko, On the hidden discrete logarithm for some polynomial stream ciphers, International Multiconference on Computer Science and Informational Technology, 20-22 October 2008, Wisla, Poland, CANA Proceedings
  18. M. Klisowski, V. Ustimenko, On the public keys based on the extremal graphs and digraphs, International Multiconference on Computer Science and Informational Technology, October 2010, Wisla, Poland, CANA Proceedings, 12 pp.
  19. J. Kotorowicz, U. Romańczuk, V. Ustimenko, Implementation of stream ciphers based on a new family of algebraic graphs, Proceedings of Federated Conference on Computer Science and Information Systems (FedCSIS), 2011, 13.
  20. L A. Grzesik, D. Kral’, L. M. Lovasz, Elusive extremal graphs, preprint (2018), ar-Xiv:1807.01141.
  21. N Hoory, A. Linial, A.Wigderson. Expander graphs and their applications, Bull. Amer. Math Soc., 43, pp 439-561, 2006.
  22. M. Polak, U. Romańczuk, V. Ustimenko, A. Wróblewska, On the applications of Extremal Graph Theory to Coding Theory and Cryptography, Electronic Notes in Discrete Mathe-matics, N 43, p. 329-342.
  23. 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 2137561, 15pages https://doi.org/10.1155/2019/2137561
  24. V. Ustimenko, M. Klisowski, On Noncommutative Cryptography with cubical multivariate maps of predictable density, Proceedings of “Computing 2019” conference, London, 16-17, July , Volume 2, Part of Advances in Intelligent Systems and Computing (AISC), volume 99, pp, 654-674.
  25. V. Ustimenko, U. Romanczuk-Polubiec, A. Wroblewska, Expanding Graph of the Extremal Graph Theory and expanded platforms of post-quantum cryptography, Annals of Computer Science and information Systems 2019, vol.19, pp 41-46.
  26. N.Alon, Eigenvalues, geometric expanders, sorting in rounds, and Ramsey Theory, Combinatorica, 6 (3), 1986, pp.207-219.
  27. D. N. Moldovyan, N. A. Moldovyan, A New Hard Problem over Non-commutative Finite Groups for Cryptographic Protocols, International Conference on Mathematical Methods, Models, and Architectures foComputer Network Security, MMM-ACNS 2010: Computer Network Security pp 183-194.
  28. V. Shpilrain, A. Ushakov, The conjugacy search problem in public key cryptography: un-necessary and insufficient, Applicable Algebra in Engineering, Communication and Computing, August 2006, Volume 17, Issue 3–4, pp 285–289.
  29. Delaram Kahrobaei, Bilal Khan, A non-commutative generalization of ElGamal key exchange using polycyclic groups, In IEEE GLOBECOM 2006 - 2006 Global Telecommu-nications Conference [4150920] http://dx.doi.org/10.1109/GLOCOM.2006.
  30. Alexei Myasnikov, Vladimir Shpilrain, Alexander Ushakov (2008). Group-based Cryptography. Berlin: Birkhäuser Verlag.
  31. Zhenfu Cao (2012), New Directions of Modern Cryptography. Boca Raton: CRC Press, Taylor Francis Group. ISBN 978-1-4665-0140-9.
  32. G.Maze., C. Monico, J. Rosenthal, Public key cryptography based on semigroup actions. Adv.Math. Commun. 1(4), 489–507 (2007).
  33. P.H. Kropholler, S.J. Pride , W.A.M. Othman K.B. Wong, P.C. Wong, Properties of cer-tain semigroups and their potential as platforms for cryptosystems, Semigroup Forum (2010) 81: 172–186.
  34. Gautam Kumar and Hemraj 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.
  35. V. A. Roman’kov, A nonlinear decomposition attack, Groups Complex. Cryptol. 8, No. 2 (2016), 197-207.
  36. V. Roman’kov, An improved version of the AAG cryptographic protocol, Groups, Complex., Cryptol, 11, No. 1 (2019), 35-42.
  37. 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, 255274, Springer, Cham (2018).
  38. B. Tsaban, Polynomial-time solutions of computational problems in noncommutative-algebraic cryptography, J. Cryptol. , 28, No. 3 (2015), 601-622.
  39. V. Ustimenko, On desynchronised multivariate algorithms of El Gamal type for stable semigroups of affine Cremona group, Theoretical and Applied Cybersecurity, National Technical University of Ukraine "Igor Sikorsky Kiev Polytechnic Institute", vol 1, 2019, pp. 22-30. 40 V.Ustimenko, On the usage of postquantum protocols defined in terms of transformation semi-groups and their homomorphisma, Theoretical and Applied Cybersecurity, National Technical University of Ukraine "Igor Sikorsky Kiev Polytechnic Institute", vol 2, 2020, pp. 32-44.