01152nas a2200133 4500008004100000245006100041210006100102260001400163490000600177520075500183100002300938700002000961856003700981 2014 eng d00aQuantum computation of discrete logarithms in semigroups0 aQuantum computation of discrete logarithms in semigroups c2014/01/10 v83 a We describe an efficient quantum algorithm for computing discrete logarithms
in semigroups using Shor's algorithms for period finding and discrete log as
subroutines. Thus proposed cryptosystems based on the presumed hardness of
discrete logarithms in semigroups are insecure against quantum attacks. In
contrast, we show that some generalizations of the discrete log problem are
hard in semigroups despite being easy in groups. We relate a shifted version of
the discrete log problem in semigroups to the dihedral hidden subgroup problem,
and we show that the constructive membership problem with respect to $k \ge 2$
generators in a black-box abelian semigroup of order $N$ requires $\tilde
\Theta(N^{\frac{1}{2}-\frac{1}{2k}})$ quantum queries.
1 aChilds, Andrew, M.1 aIvanyos, GĂˇbor uhttp://arxiv.org/abs/1310.6238v2