Are Schnorr's algorithm really subject to q-computer attacks?

Question

I was wondering whether quantum-computers really break Schnorr's signature scheme. Schor's algorithm works via the quantum Fourier transform, which reveals the cycle time and thus phi. However, with a multiplicative group mod $q$, a prime, everyone knows the cycle time, but that isn't the problem (unlike RSA). The problem is in finding a specific value.

Unlike in RSA, where you must FACTOR a number, Schnorr's signature relies on the discrete logarithm problem. When you plug 15 into Schor's, you get 8 when you measure the state. Then you use this to factor the number. However, in Schnorr's, you may get 16 when you plug in 17, but this isn't helpful. You are trying to find what item in the polynomial ring generator 2 mod 17 is 9. I'm pretty sure the cycle time doesn't help, we already knew that.

Where am I going wrong?

Answer 1

The quantum Fourier transform is more powerful than a black box that returns the period of a cyclic group.

A more general application is the hidden abelian subgroup problem. In the case of discrete logarithms where we want so find $x$ when $y=g^x\mod q$ in a group order $\ell$, we consider the abelian group $C_\ell\times C_\ell$ and the hidden subgroup of elements of our Schnorr group of the form $g^ay^b\mod q$. The abelian Fourier transform will return the analogy of the period which in this case is a pair of integers $(r,s)$ such that $g^ry^s=1\mod q$. From this the discrete logarithm is easily calculated as $-r/s\pmod\ell$.

You might like to read this more detailed answer specific to elliptic curves.