LOGARITHMIC SIGNATURES FOR ABELIAN GROUPS AND THEIR FACTORIZATION

Svaba, Pavol; Trung, Tran van; Wolf, Paul

doi:10.2478/tmmp-2013-0033

Abstract

Factorizable logarithmic signatures for finite groups are the essential component of the cryptosystems MST₁ and MST₃. 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.

References

[1] BLACKBURN, S. R.-CID, C.-MULLAN, C.: Cryptanalysis of the MST3 public keycryptosystem, J. Math. Crypt. 3 (2009), 321-338.
Search in Google Scholar
[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.10.1007/s00145-008-9033-y
Search in Google Scholar
[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.10.1007/BF02924858
Search in Google Scholar
[4] MAGLIVERAS, S. S.: A cryptosystem from logarithmic signatures of finite groups, in: Proc. of the 29th Midwest Symposium on Circuits and Systems (M. Ismail, ed.), Lincoln, NE, 1986, Elsevier Publ. Comp., 1986, pp. 972-975.
Search in Google Scholar
[5] MAGLIVERAS, S. S.-MEMON, N. D.: Random permutations from logarithmic signatures, in: Computing in the 90’s, 1st Great Lakes Comp. Sci. Conf. (N.A. Sherwani et al., eds.), Kalamazoo, USA, 1989, Lecture Notes in Comput. Sci., Vol. 507 Springer-Verlag, Berlin, 1989, pp. 91-97.
Search in Google Scholar
[6] MAGLIVERAS, S. S.-MEMON, N. D.: The algebraic properties of cryptosystem PGM, J. Cryptology 5 (1992), 167-183.10.1007/BF02451113
Search in Google Scholar
[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.10.1007/s00145-001-0018-3
Search in Google Scholar
[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.
Search in Google Scholar
[9] MARQUARDT, P.-SVABA, P.-TRAN VAN TRUNG: Pseudorandom number generatorsbased on random covers for finite groups, Des. Codes Cryptogr. 64 (2012), 209-220.10.1007/s10623-011-9485-1
Search in Google Scholar
[10] SVABA, P.-TRAN VAN TRUNG: On generation of random covers for finite groups, Tatra Mt. Math. Publ. 37 (2007), 105-112.
Search in Google Scholar
[11] SVABA, P.-TRAN VAN TRUNG: Public key cryptosystem MST3: cryptanalysis andrealization, J. Math. Crypto. 4 (2010), 271-315.10.1515/jmc.2010.011
Search in Google Scholar
[12] SZAB´ O, S.: Topics in Factorization of Abelian Groups. Birkh¨auser Verlag, Berlin, 2004.10.1007/978-93-86279-22-4
Search in Google Scholar
[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.
Search in Google Scholar

LOGARITHMIC SIGNATURES FOR ABELIAN GROUPS AND THEIR FACTORIZATION

Abstract

Paradigm

My account