×

Logarithmic signatures for abelian groups and their factorization. (English) Zbl 1345.94089

Summary: Factorizable logarithmic signatures for finite groups are the essential component of the cryptosystems MST\(_1\) and MST\(_3\). The problem of finding efficient algorithms for factoring group elements with respect to a given class of logarithmic signatures is therefore of vital importance in the investigation of these cryptosystems. In this paper we are concerned about the factorization algorithms with respect to transversal and fused transversal logarithmic signatures for finite abelian groups. More precisely we present algorithms and their complexity for factoring group elements with respect to these classes of logarithmic signatures. In particular, we show a factoring algorithm with respect to the class of fused transversal logarithmic signatures and also its complexity based on an idea of Blackburn, Cid and Mullan for finite abelian groups.

MSC:

94A60 Cryptography
20K01 Finite abelian groups
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] BLACKBURN, S. R.-CID, C.-MULLAN, C.: Cryptanalysis of the MST3 public keycryptosystem, J. Math. Crypt. 3 (2009), 321-338. · Zbl 1185.94046 · doi:10.1515/JMC.2009.020
[2] LEMPKEN, W.-MAGLIVERAS, S. S.-TRAN VAN TRUNG-WEI, W.: A public keycryptosystem based on non-abelian finite groups, J. Cryptology 22 (2009), 62-74. · Zbl 1168.94005 · doi:10.1007/s00145-008-9033-y
[3] MAGLIVERAS, S. S.-OBERG, B. A.-SURKAN, A. J.: A new random number generatorfrom permutation groups, Rend. Sem. Mat. Fis. Milano 54 (1984), 203-223. · Zbl 0621.65001 · doi:10.1007/BF02924858
[4] MAGLIVERAS, S. S.: A cryptosystem from logarithmic signatures of finite groups, in: Proc. of the 29th Midwest Symposium on Circuits and Systems , Lincoln, NE, 1986, Elsevier Publ. Comp., 1986, pp. 972-975.
[5] MAGLIVERAS, S. S.-MEMON, N. D.: Random permutations from logarithmic signatures, in: Computing in the 90’s, 1st Great Lakes Comp. Sci. Conf. , Kalamazoo, USA, 1989, Lecture Notes in Comput. Sci., Vol. 507 Springer-Verlag, Berlin, 1989, pp. 91-97.
[6] MAGLIVERAS, S. S.-MEMON, N. D.: The algebraic properties of cryptosystem PGM, J. Cryptology 5 (1992), 167-183. · Zbl 0763.94014 · doi:10.1007/BF02451113
[7] MAGLIVERAS, S. S.-STINSON, D. R.-TRAN VAN TRUNG: New approaches to designingpublic key cryptosystems using one-way functions and trapdoors in finite groups, J. Cryptology 15 (2002), 285-297. · Zbl 1020.94010 · doi:10.1007/s00145-001-0018-3
[8] MAGLIVERAS, S. S.-SVABA, P.-TRAN VAN TRUNG-ZAJAC, P.: On the securityof a realization of cryptosystem MST3, Tatra Mt. Math. Publ. 41 (2008), 1-13.
[9] MARQUARDT, P.-SVABA, P.-TRAN VAN TRUNG: Pseudorandom number generatorsbased on random covers for finite groups, Des. Codes Cryptogr. 64 (2012), 209-220. · Zbl 1347.65009 · doi:10.1007/s10623-011-9485-1
[10] SVABA, P.-TRAN VAN TRUNG: On generation of random covers for finite groups, Tatra Mt. Math. Publ. 37 (2007), 105-112. · Zbl 1240.94092
[11] SVABA, P.-TRAN VAN TRUNG: Public key cryptosystem MST3: cryptanalysis andrealization, J. Math. Crypto. 4 (2010), 271-315. · Zbl 1203.94125 · doi:10.1515/JMC.2010.011
[12] SZABÓ, S.: Topics in Factorization of Abelian Groups. Birkhäuser Verlag, Berlin, 2004. · Zbl 1086.20026
[13] VASCO, M. I.G.-DEL POZO, A.I.P.-DUARTE, P.T.: A note on the security of MST3 Des. Codes Cryptogr. 55 (2010), 189-200. · Zbl 1210.94090
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.