Logarithmic signatures for abelian groups and their factorization

Abstract

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