DLP in semigroups: Algorithms and lower bounds

Abstract

The discrete logarithm problem (DLP) in semigroups has attracted some interests and serves as the foundation of many cryptographic schemes. In this work, we study algorithms and lower bounds for DLP in semigroups. First, we propose a variant of the deterministic algorithm for solving the cycle length of torsion elements and show the lower bound of computing the DLP in a semigroup. Then, we propose an algorithm for solving the multiple discrete logarithm (MDL) problem in the semigroup and give the lower bound for solving the MDL problem by considering the MDL problem in the generic semigroup model. Besides, we solve the multidimensional DLP and product DLP in the semigroup.

Keywords

• discrete logarithm problem
• semigroups
• torsion elements
• cycle length
• lower bounds
• 11t71
• 11y16