Quantum computation of discrete logarithms in semigroups
This work addresses cryptographic security for systems relying on semigroup discrete logarithms, revealing vulnerabilities to quantum attacks but identifying hard variants, which is incremental in extending quantum cryptanalysis.
The paper tackles the problem of computing discrete logarithms in semigroups by proposing an efficient quantum algorithm that breaks cryptosystems based on this hardness, showing they are insecure against quantum attacks, while also demonstrating that some generalizations remain hard, with query complexity results like $ ilde \Theta(N^{ rac{1}{2}- rac{1}{2k}})$ for certain problems.
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 Θ(N^{\frac{1}{2}-\frac{1}{2k}})$ quantum queries.