International Association for Cryptologic Research
For Discrete Logarithm Problem (DLP) based cryptography, it is desirable to find efficiently implementable groups for which sub-exponential algorithms for the DLP are not available. The authors present a polynomial-time reduction of the discrete logarithm problem in any periodic (a.k.a. torsion) semigroup (Semigroup DLP) to the classic DLP in a subgroup of the same semigroup. It follows that semigroup DLP can be solved in polynomial time by quantum computers, and that semigroup DLP has sub-exponential algorithms whenever the classic DLP in the corresponding groups has sub-exponential algorithms.