logo

SCIENCE CHINA Information Sciences, Volume 60, Issue 5: 052106(2017) https://doi.org/10.1007/s11432-015-5479-3

Minimum length key in MST cryptosystems

More info
  • ReceivedOct 22, 2015
  • AcceptedDec 8, 2015
  • PublishedSep 13, 2016

Abstract

As a special factorization category of finite groups, logarithmic signature (LS) is used as the main component of cryptographic keys that operate within secret key cryptosystems such as PGM and public key cryptosystems like $MST_1$, $MST_2$ and $MST_3$. An LS with the shortest length is called a minimal logarithmic signature (MLS) that constitutes of the smallest sized blocks and offers the lowest complexity, and is therefore desirable for cryptographic constructions. However, the existence of MLSs for finite groups should be firstly taken into an account. The MLS conjecture states that every finite simple group has an MLS. If it holds, then by the consequence of Jordan-Hölder Theorem, every finite group would have an MLS. In fact, many cryptographers and mathematicians are keen for solving this problem. Some effective work has already been done in search of MLSs for finite groups. Recently, we have made some progress towards searching a minimal length key for MST cryptosystems and presented a theoretical proof of MLS conjecture.


Funded by

National Natural Science Foundation of China(61370194)

NSFC A3 Foresight Program(61411146001)

National Natural Science Foundation of China(61373131)

National Natural Science Foundation of China(61502048)


Acknowledgment

Acknowledgments

This work was supported by National Natural Science Foundation of China (Grant Nos. 61502048, 61370194, 61373131) and NSFC A3 Foresight Program (Grant No. 61411146001). This work was also partially supported by PAPD and CICAEET.


References

[1] Shor P. Polynomial time algorithms for prime factorization and discrete logarithms on quantum computers. SIAM J Comput, 1997, 26: 1484-1509 CrossRef Google Scholar

[2] Proos J, Zalka C. Shor's discrete logarithm quantum algorithm for elliptic curves. Quantum Inf Comput, 2003, 3: 317-344 Google Scholar

[3] Blaser M. Noncommutativity makes determinants hard. Electr Coll Comp Complex Report. No. 142. 2012. Google Scholar

[4] Rotteler M. Quantum algorithms: a survey of some recent results. Inf Forsch Entw, 2006, 21: 3-20 CrossRef Google Scholar

[5] Wagner N, Magyarik M. A public-key cryptosystem based on the word problem. In: Proceedings of CRYPTO'84 on Advances in Cryptology. Berlin: Springer, 1985. 19--36. Google Scholar

[6] Ko K, Lee S, Cheon J, et al. New public-key cryptosystem using braid groups. In: Proceedings of 20th Annual International Cryptology Conference on Advances in Cryptology, Santa Barbara, 2000. 166--183. Google Scholar

[7] Eick B, Kahrobaei D. Polycyclic groups: a new platform for cryptology. arXiv:math/0411077. Google Scholar

[8] Shpilrain V, Ushakov A. Thompson's group and public key cryptography. In: Proceedings of 3rd International Conference on Applied Cryptography and Network Security, New York, 2005. 151--164. Google Scholar

[9] Kahrobaei D, Koupparis C, Shpilrain V. Public key exchange using matrices over group rings. Groups Complexity Cryptol, 2013, 5: 97-115 Google Scholar

[10] Magliveras S S. A cryptosystem from logarithmic signatures of finite groups. In: Proceedings of 29th Midwest Symposium on Circuits and Systems. Amsterdam: Elsevier Publishing Company, 1986. 972--975. Google Scholar

[11] Magliveras S S, Memon N D. Properties of cryptosystem PGM. In: Proceedings of 9th Annual International Cryptology Conference, Santa Barbara, 1989. 447--460. Google Scholar

[12] Magliveras S S, Memon N D. Complexity tests for cryptosystem PGM. Congr Numer, 1990, 79: 61-68 Google Scholar

[13] Magliveras S S, Memon N D. Algebraic properties of cryptosystem PGM. J Cryptol, 1992, 5: 167-183 Google Scholar

[14] Caranti A, Volta D F. The round functions of cryptosystem PGM generate the symmetric group. Des Codes Cryptogr, 2006, 38: 147-155 CrossRef Google Scholar

[15] Magliveras S S, Stinson D R, van Trung T. New approaches to designing public key cryptosystems using one-way functions and trapdoors in finite groups. J Cryptol, 2002, 15: 285-297 CrossRef Google Scholar

[16] Lempken W, Magliveras S S, van Trung T, et al. A public key cryptosystem based on non-abelian finite groups. J Cryptol, 2009, 22: 62-74 CrossRef Google Scholar

[17] Higman G. Suzuki 2-groups. Ill J Math, 1963, 7: 79-96 Google Scholar

[18] Magliveras S S, Svaba P, van Trung T, et al. On the security of a realization of cryptosystem $MST_3$. Tatra Mt Math Publ, 2008, 41: 1-13 Google Scholar

[19] Blackburn S R, Cid C, Mullan C. Cryptanalysis of the $MST_3$ public key cryptosystem. J Math Crypt, 2009, 3: 321-338 Google Scholar

[20] González Vasco M I, Pérez del Pozo A L, Duarte P T. A note on the security of $MST_3$. Des Codes Cryptogr, 2010, 55: 189-200 CrossRef Google Scholar

[21] Svaba P, van Trung T. Public key cryptosystem MST3: cryptanalysis and realization. J Math Cryptol, 2010, 4: 271-315 Google Scholar

[22] Hong H B, Li J, Wang L C, et al. A digital signature scheme based on $MST_3$ cryptosystem. Math Probl Eng, 2014, 2014: 630421-315 Google Scholar

[23] González Vasco M I, Rötteler M, Steinwandt R. On minimal length factorizations of finite groups. Exp Math, 2003, 12: 1-12 CrossRef Google Scholar

[24] Holmes P E. On minimal factorisations of sporadic groups. Exp Math, 2004, 13: 435-440 CrossRef Google Scholar

[25] Lempken W, van Trung T. On minimal logarithmic signatures of finite groups. Exp Math, 2005, 14: 257-269 CrossRef Google Scholar

[26] Singhi N, Singhi N, Magliveras S S. Minimal logarithmic signatures for finite groups of Lie type. Des Codes Cryptogr, 2010, 55: 243-260 CrossRef Google Scholar

[27] Singhi N, Singhi N. Minimal logarithmic signatures for classical groups. Des Codes Cryptogr, 2011, 60: 183-195 CrossRef Google Scholar

[28] Hong H B, Wang L C, Yang Y X, et al. All exceptional groups of Lie type have minimal logarithmic signatures. Appl Algebr Eng Commun Comput, 2014, 25: 287-296 CrossRef Google Scholar

[29] Hong H B, Wang L C, Yang Y X. Minimal logarithmic signatures for the unitary group $U_n(q)$. Des Codes Cryptogr, 2015, 77: 179-191 CrossRef Google Scholar

[30] Hong H B, Wang L C, Ahmad H, et al. Minimal logarithmic signatures for a type of classical groups. arXiv:1507.01163. Google Scholar

[31] Hong H B, Wang L C, Ahmad H, et al. Minimal logarithmic signatures for sporadic groups. arXiv:1507.01162. Google Scholar

[32] González Vasco M I, Steinwandt R. Obstacles in two public key cryptosystems based on group factorizations. Tatra Mt Math Publ, 2002, 25: 23-37 Google Scholar

[33] Conway J, Curtis R, Norton S, et al. Atlas of Finite Groups. Oxford: Clarendon Press, 1985. Google Scholar

[34] Cossidente A, de Resmini M J. Remarks on singer cyclic groups and their normalizers. Des Codes Cryptogr, 2004, 32: 97-102 CrossRef Google Scholar

[35] Hestenes M D. Singer groups. Can J Math, 1970, 22: 492-513 CrossRef Google Scholar

[36] Thas J A. Ovoids and spreads of finite classical polar spaces. Geom Dedic, 1981, 10: 135-143 CrossRef Google Scholar

[37] Kantor W M. Spreads, translation planes and Kerdock sets. I. SIAM J Algebr Discret Meth, 1982, 3: 151-165 CrossRef Google Scholar

[38] Wilson R A. The Finite Simple Groups. London: Springer-Verlag, 2009. Google Scholar

[39] Rahimipour A R, Ashrafi A R, Gholami A. The existence of minimal logarithmic signatures for some Suzuki and simple unitary. Cryptogr Commun, 2015, 7: 535-iffalse CrossRef Google Scholar

[40] Magliveras S S. Secret and public-key cryptosystems from group factorizations. Tatra Mt Math Publ, 2002, 25: 11-22 Google Scholar

[41] Bohli J M, Steinwandt R, González Vasco M I, et al. Weak keys in $MST_1$. Des Codes Cryptogr, 2005, 37: 509-524 CrossRef Google Scholar

[42] González Vasco M I, Mart\'{\i}nez C, Steinwandt R. Towards a uniform description of several group based cryptographic primitives. Des Codes Cryptogr, 2004, 33: 215-226 CrossRef Google Scholar

[43] Marquardt P, Svaba P, van Trung T. Pseudorandom number generators based on random covers for finite groups. Des Codes Cryptogr, 2012, 64: 209-fi CrossRef Google Scholar

Copyright 2019 Science China Press Co., Ltd. 《中国科学》杂志社有限责任公司 版权所有

京ICP备18024590号-1