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

Luke Bright

5/2/24, 10:15 PM

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?

1 + 2

cryptanalysis

quantum-cryptanalysis

shors-algorithm

bmm6o

5/3/24, 12:19 AM

Related: https://bitcoin.stackexchange.com/questions/57965/are-schnorr-signatures-quantum-computer-resistant

Luke Bright

5/3/24, 12:58 AM

Yeah, saw that, but most were referencing Shor's algorithm. Thanks though!

Score:3

Crypto

Daniel S

5/3/24, 6:11 AM

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.

+ 0

Elon Musk

I sit in a Tesla and translated this thread with Ai:

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

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.