Cryptosystems based on logarithmic signatures and covers of finite groups

Eduard Primenko, Andrey Rybkin

Abstract


 In this paper, we survey a cryptographic direction of post-quantum cryptography based on logarithmic signatures and covers of finite groups. These mathematical structures allows designing cryptosystems with security based on hardness of the factorization problem in finite group. This problem is assumed computationally hard even in post-quantum era. We give basic definitions and functions related to logarithmic signatures and covers of finite groups. Relations between these functions and the factorization problem in finite group are explained. We describe some logarithmic signatures generation methods and consider the hardness of the factorization problem in each case. We give a description of the existing cryptosystems based on logarithmic signatures and covers of finite groups in chronological order. These cryptographic systems applicable for such purposes as data ciphering, digital signing or pseudo random number generation. We mainly focus on cryptosystem MST3 that is the most perspective ciphering system in the direction. Description of Suzuki 2-groups traditionally used as a finite group in cryptographic system MST3 is given. A toy example of MST3 based on Suzuki 2-group is demonstrated. We also consider the main analysis results of existing cryptosystems based on logarithmic signatures and covers of finite groups.


Full Text:

PDF (Russian)

References


P. Svaba, T. van Trung, P. Wolf, “Logarithmic signatures for Abelian groups and their factorization”, Tatra Mt. Math. Publ., 57:1 (2013), 21–33.

S.S. Magliveras, “A cryptosystem from logarithmic signatures of finite groups”, Proceedings of the 29th Midwest Symposium on Circuits and Systems, 1986, 972–975.

S.S. Magliveras, D.R. Stinson, T. van Trung, “New approaches to designing public key cryptosystems using one-way functions and trapdoors in finite groups”, Journal of cryptology, 15:4 (2002), 285–297.

W. Lempken, T. van Trung, S.S. Magliveras, W. Wei, “A public key cryptosystem based on non-Abelian finite groups”, J. Cryptology, 22:1 (2009), 62–74.

G. Higman, “Suzuki 2-groups”, Illinois J. Math., 7:1 (1963), 79–96.

P. Svaba, T. van Trung, “Public key cryptosystem MST3: cryptanalysis and realization”, Journal of Mathematical Cryptology, 4:3 (2010), 271–315.

H. Hong, J. Li, L. Wang, Y. Yang, X. Niu, “A Digital Signature Scheme Based on MST3 Cryptosystems”, Mathematical Problems in Engineering, 2014.

P. Svaba, P. Marquardt, T. van Trung, “MSTg: Cryptographically strong pseudorandom number generator and its realization”, 2013.

S.S. Magliveras, N.D. Memon, “Algebraic properties of cryptosystem PGM”, Journal of cryptology, 5:3 (1992), 167–183.

M.I.G. Vasco, R. Steinwandt, “Obstacles in two public key cryptosystems based on group factorizations”, Tatra Mt Math. Publ., 25 (2002), 23–37.

J.-M. Bohli, R. Steinwandt, M.I.G. Vasco, C. Martinez, “Weak keys in MST1”, Designs, Codes and Cryptography, 37:3 (2005), 509–524.

S.S. Magliveras, P. Svaba, T. van Trung, P. Zajac, “On the security of a realization of cryptosystem MST3”, Tatra Mt. Math. Publ., 41 (2008), 65–78.

M.I.G. Vasco, A.L.P. del Pozo, P.T. Duarte, “A note on the security of MST3”, Des. Codes and Cryptography, 55:2-3 (2010), 189–200.

S.R. Blackburn, C. Cid, C. Mullan, “Cryptanalysis of the MST3 public key cryptosystem”, J. Math. Cryptology, 3:4 (2009), 321–338.

A.S. Rybkin, “Investigation of the cryptosystem MST3 based on a Suzuki 2-group”, Discrete Mathematics and Applications, 25:3 (2015), 157–177.

C. Song, M. Xu, C. Tang, “Pseudorandom generators based on subcovers for finite groups”, International Conference on Information Security and Cryptology, 2011, 379–392.

P. Marquardt, P. Svaba, T. van Trung, “Pseudorandom number generators based on random covers for finite groups”, Designs, Codes and Cryptography, 64:1-2 (2012), 209–220.

W. Lempken, T. van Trung, “On minimal logarithmic signatures of finite groups”, Experimental Mathematics, 14:3 (2005), 257–269.

N. Singhi, N. Singhi, S.S. Magliveras, “Minimal logarithmic signatures for finite groups of Lie type”, Designs, Codes and Cryptography, 55:2-3 (2010), 243–260.

N. Singhi, N. Singhi, “Minimal logarithmic signatures for classical groups”, Designs, Codes and Cryptography, 60:2 (2011), 183–195.

N. Singhi, “The existence of minimal logarithmic signatures for classical groups”, 2011, 177–192.

N. Singhi, “On the minimal logarithmic signature conjecture”, 2011.

H. Hong, L. Wang, Y. Yang, H. Ahmad, “All exceptional groups of lie type have minimal logarithmic signatures”, Applicable Algebra in Engineering, Communication and Computing, 25:4 (2014), 287–296.

H. Hong, L. Wang, Y. Yang, “Minimal logarithmic signatures for the unitary group Un(q)”, Designs, Codes and Cryptography, 77:1 (2015), 179–191.

H. Hong, L. Wang, H. Ahmad, J. Li, Y. Yang, “Minimal logarithmic signatures for sporadic groups”, arXiv preprint arXiv:1507.01162, 2015.

H. Hong, L. Wang, H. Ahmad, J. Shao, Y. Yang, “Minimal logarithmic signatures for one type of classical groups”, Applicable Algebra in Engineering, Communication and Computing, 28:2 (2017), 177–192.

B. Baumeister, J.-H. de Wiljes, “Aperiodic logarithmic signatures”, Journal of Mathematical Cryptology, 6:1 (2012), 21–37.

R. Staszewski, T. van Trung, “Strongly aperiodic logarithmic signatures”, Journal of Mathematical Cryptology, 7:2 (2013), 147–179.

T. van Trung, “Construction of strongly aperiodic logarithmic signatures”, Journal of Mathematical Cryptology, 12:1 (2018), 23–35.


Refbacks

  • There are currently no refbacks.


Abava  Absolutech Convergent 2020

ISSN: 2307-8162