Logo PTI Logo FedCSIS

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

Annals of Computer Science and Information Systems, Volume 32

On D(n; q) quotients of large girth and hidden homomorphism based cryptographic protocols

,

DOI: http://dx.doi.org/10.15439/2022F54

Citation: Communication Papers of the 17th Conference on Computer Science and Intelligence Systems, M. Ganzha, L. Maciaszek, M. Paprzycki, D. Ślęzak (eds). ACSIS, Vol. 32, pages 199–206 ()

Full text

Abstract. Noncommutative cryptography is based on applications of algebraic structures like noncommutative groups,semigroups, and noncommutative rings. Its intersection withMultivariate cryptography contains studies of cryptographicapplications of subsemigroups and subgroups of affine Cremona semigroups defined over finite commutative rings. Efficientlycomputed homomorphisms between stable subsemigroups of affine Cremona semigroups can be used in tame homomorphisms protocols schemes and their inverse versions. The implementationscheme with the sequence of subgroups of affine Cremona group that defines the projective limit was already suggested. We present the implementation of another scheme that uses two projective limits which define two different infinite groups and the homomorphism between them. The security of the corresponding algorithm is based on complexity of the decomposition problem for an element of affine Cremona semigroup into a product of given generators. These algorithms may be used in postquantum technologies.

References

  1. M. Anshel, M. Anshel, and D. Goldfeld. An algebraic method for public-key cryptography. Math. Res. Lett., 6:287–291, 1999.
  2. S. Blackburn and S. Galbraith. Cryptanalysis of two cryptosystems based on group actions. In K. Lam, C. Xing, and E. Okamoto, editors, Advances in Cryptology – ASIACRYPT ’99, Lecture Notes in Computer Science, pages 52–61. Springer, 1999.
  3. Z. Cao. New Directions of Modern Cryptography. CRC Press, 2012.
  4. J. Ding, J. E. Gower, and D. S. Schmidt. Multivariate Public Key Cryptosystems. Advances in Information Security. Springer, 2006.
  5. B. Fine, M. Habeeb, D. Kahrobaei, and G. Rosenberger. Aspects of nonabelian group based cryptography: A survey and open problems. https://arxiv.org/abs/1103.4093 [cs.CR], 2011. http://arxiv.org/.
  6. L. Goubin, J. Patarin, and B.-Y. Yang. Multivariate cryptography. In Encyclopedia of Cryptography and Security, pages 824–828. Springer US, Boston, MA, 2011.
  7. D. Kahrobaei and B. Khan. A non-commutative generalization of elgamal key exchange using polycyclic groups. In IEEE GLOBECOM 2006 - 2006 Global Telecommunications Conference, 12 2006.
  8. M. Klisowski. Zwiększenie bezpieczeństwa kryptograficznych algoryt mów wielu zmiennych bazujacych na algebraicznej teorii grafów. PhD thesis, Politechnika Częstochowska, 2015.
  9. M. Klisowski and V. Ustimenko. On the comparison of cryptographical properties of two different families of graphs with large cycle indicator. Mathematics in Computer Science, 6(2):181–198, 2012.
  10. M. Klisowski and V. Ustimenko. Graph based cubical multivariate maps and their cryptographical applications. In L. Beshaj, T. Shaska, and E. Zhupa, editors, Advances on Superelliptic Curves and their Applications, volume 41 of NATO Science for Peace and Security Series - D: Information and Communication Security, pages 305–327. IOS Press, 2015.
  11. 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 M. Bellare, editor, Advances in Cryptology — CRYPTO 2000, pages 166–183, Berlin, Heidelberg, 2000. Springer Berlin Heidelberg.
  12. N. Koblitz. Algebraic Aspects of Cryptography. Springer-Verlag, Berlin, Heidelberg, 1998.
  13. 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, 81(1):172–186, 2010.
  14. G. Kumar and H. Saini. Novel noncommutative cryptography scheme using extra special group. Security and Communication Networks, 2017:1–21, 01 2017.
  15. F. Lazebnik, V. A. Ustimenko, and A. J. Woldar. A new series of dense graphs of high girth. Bull. Amer. Math. Soc., 32:73–79, 1995.
  16. J. A. Lopez-Ramos, J. Rosenthal, D. Schipani, and R. Schnyder. Group key management based on semigroup actions. J. Algebra Appl., 16(8), 2017.
  17. G. Maze, C. Monico, and J. Rosenthal. Public key cryptography based on semigroup actions. Adv. Math. Commun., 1(4):489–507, 2007.
  18. R. J. McEliece. A public-key cryptosystem based on algebraic coding theory. DSN Progress Report, 44:114–116, Jan 1978.
  19. D. N. Moldovyan and N. A. Moldovyan. A new hard problem over non-commutative finite groups for cryptographic protocols. In I. Kotenko and V. Skormin, editors, Computer Network Security, pages 183–194, Berlin, Heidelberg, 2010. Springer Berlin Heidelberg.
  20. A. Myasnikov, V. Shpilrain, and A. Ushakov. Group-based Cryptography. Advanced Courses in Mathematics — CRM Barcelona. Springer Basel AG, 2008.
  21. A. Myasnikov, V. Shpilrain, and A. Ushakov. Non-commutative Cryptography and Complexity of Group-theoretic Problems. Mathematical surveys and monographs. American Mathematical Society, 2011.
  22. E. Sakalauskas, P. Tvarijonas, and A. Raulynaitis. Key agreement protocol (kap) using conjugacy and discrete logarithm problems in group representation level. Informatica, Lith. Acad. Sci., 18:115–124, 01 2007.
  23. V. Shpilrain and A. Ushakov. The conjugacy search problem in public key cryptography: Unnecessary and insufficient. Applicable Algebra in Engineering, Communication and Computing, 17(3):285–289, 2006.
  24. V. Ustimenko. On linguistic dynamical systems, families of graphs of large girth, and cryptography. J. Math. Sci., 140(3):461–471, 2007.
  25. V. Ustimenko. On desynchronised multivariate el gamal algorithm. Cryptology ePrint Archive, Report 2017/712, 2017. https://eprint.iacr.org/2017/712.
  26. V. Ustimenko. On the families of stable multivariate transformations of large order and their cryptographical applications. Tatra Mt. Math Publ., 70:107–117, 2017.
  27. V. Ustimenko. On new symbolic key exchange protocols and cryptosystems based on a hidden tame homomorphism. Reports of the National Academy of Sciences of Ukraine, (10):26–36, 2018.
  28. V. Ustimenko. On semigroups of multiplicative cremona transformations and new solutions of post quantum cryptography. Cryptology ePrint Archive, Report 2019/133, 2019. https://eprint.iacr.org/2019/133.
  29. V. Ustimenko and M. Klisowski. On noncommutative cryptography and homomorphism of stable cubical multivariate transformation groups of infinite dimensional affine spaces. Cryptology ePrint Archive, Report 2019/593, 2019. https://eprint.iacr.org/2019/593.
  30. V. Ustimenko and M. Klisowski. On noncommutative cryptography with cubical multivariate maps of predictable density. In K. Arai, R. Bhatia, and S. Kapoor, editors, Intelligent Computing: Proceedings of the 2019 Computing Conference, Volume 2, number 998 in Advances in Intelligent Systems and Computing, pages 654–674. Springer, 2019.
  31. V. Ustimenko and U. Romańczuk. On extremal graph theory, explicit algebraic constructions of extremal graphs and corresponding turing encryption machines. In Artificial Intelligence, Evolutionary Computing and Metaheuristics, pages 257–285. Springer, 2013.
  32. V. Ustimenko, U. Romańczuk-Polubiec, A. Wróblewska, M. K. Polak, and E. Zhupa. On the constructions of new symmetric ciphers based on nonbijective multivariate maps of prescribed degree. Secur. Commun. Netw., 2019, 2019.
  33. V. Ustimenko. On new results of Extremal Graph Theory and Postquantum Cryptography. International Algebraic Conference “At the End of the Year 2021”, December 27-28, 2021 Kyiv, Ukraine ABSTRACTS, p. 29.
  34. V. Ustimenko. On new results on Extremal Graph Theory, Theory of Algebraic Graphs and their applications in Cryptography and Coding Theory. Cryptology ePrint Archive, Report 2022/296, 2022. https://eprint.iacr.org/2022/296.
  35. V. A. Ustimenko. Coordinatization of regular tree and its quotients. In P. Engel and H. Syta, editors, Voronoï’s Impact on Modern Science, number 2 in Proceedings of the institute of mathematics of the national academy of sciences of Ukraine. Institute of Mathematics, National Academy of Sciences of Ukraine, 1998.
  36. V. A. Ustimenko. Graphs with special arcs and cryptography. Acta Applicandae Mathematicae, 74, 2002.
  37. V. A. Ustimenko. Maximality of affine group, and hidden graph cryptosystems. Alg. Dis. Mthm., 2005(1):133–150, 2005.
  38. V. A. Ustimenko. On graph-based cryptography and symbolic computations. Serdica Journal of Computing, 1(2):131–156, 2007.
  39. N. R. Wagner and M. R. Magyarik. A public key cryptosystem based on the word problem. In Proceedings of CRYPTO 84 on Advances in Cryptology, pages 19–36, New York, NY, USA, 1985. Springer-Verlag New York, Inc.
  40. V. Ustimenko, S. Kotorowicz, and U. Romanczuk. On the implementation of stream ciphers based on a new family of algebraic graphs. In M. Ganzha, L. A. Maciaszek, and M. Paprzycki, editors, Federated Conference on Computer Science and Information Systems, FedCSIS 2011, Szczecin, Poland, 18-21 September 2011, Proceedings, pages 485–490, 2011.
  41. V. Ustimenko, U. Romanczuk-Polubiec, A. Wróblewska, M. Polak, and E. Zhupa. On the implementation of new symmetric ciphers based on non-bijective multivariate maps. In M. Ganzha, L. A. Maciaszek, and M. Paprzycki, editors, Proceedings of the 2018 Federated Conference on Computer Science and Information Systems, FedCSIS 2018, Poznań, Poland, September 9-12, 2018, volume 15 of Annals of Computer Science and Information Systems, pages 397–405, 2018.