Taproot, a Bitcoin protocol upgrade that includes support for Schnorr signatures, was proposed to the Bitcoin Development Mailing List in January 2020 and activated through a soft fork in November 2021. It made Schnorr signatures available for Taproot outputs, while earlier output types continued to use ECDSA. The linearity of Schnorr signatures also enables efficient key-aggregation protocols such as MuSig.
Schnorr signatures are actually easier to understand than ECDSA. That makes sense, since DSA was created specifically to work around Schnorr’s patent when NIST was establishing a digital signature standard, and ECDSA is the elliptic curve variant of DSA.
This post introduces the Schnorr signature scheme and explains the role of the discrete logarithm problem (DLP) in its security. By the end of this post, readers should understand how Schnorr signatures work, and how their security is connected to an underlying computational assumption.
Readers are assumed to have a basic familiarity with abstract algebra. Otherwise, it may be helpful to first read the Abstract Algebra section of the Wuille's libsecp256k1 tutorial.
Let \[ C = (\{O, G, \cdots, (p - 1)G\}, +) \] be cyclic group generated by \( G \). (Notation: \( 2G = G + G \))
Then the set of the coefficients of the elements of \(C\) with respect to \(G\) is \[ \mathbb Z/p\mathbb Z = \{0,1,\cdots,p-1\}. \]
It is well known that it forms a field if and only if \(p\) is prime, which also assumed here.
Now for some secret key \( d \in \mathbb Z/p\mathbb Z\), corresponding public key \( E \) is yielded by \[ E = (p - d)G \in C \] while \(d\) should be nonzero.
You might pause here. Isn't it possible to determine \(d\) from \(E\) immediately? In fact, the algorithm's cryptographic foundation rests on choosing group \(C\) having difficulty deriving \(d\) from \((p-d)G\) (where \(p\) and \(G\) is also known).
In the subsequent signing process, the scheme is designed so that it is infeasible to determine \(d\) from the publicly known values \(p\), \(G\), \(E\), and the generated signature \(\mathtt{SIGN}_d(M)\). Where \(M\) is target message to sign.
Now take nonzero random nonce \(k \in \mathbb Z/p\mathbb Z\). Then for \(x = H(kG || M)\), \[ \mathtt{SIGN}_d(M) = (x, k + xd). \]
Where \(H\) is cryptographic hash function that normalizes arbitrary length \(kG || M\) (This is simply a concatenation operation. It varies by implementation, and it just needs to produce different hashes if \(M\) is the same and \(kG\) is different) to nonzero element of \(\mathbb Z/p\mathbb Z\).
Can the difficulty of determining \(d\) be increased from knowing \((x, k+xd)\)?
Given \(E\), \(G\), \(x\), and \(k + xd\) public, also \begin{equation} \begin{split} R &= xE + (k + xd)G \\ &= x(p-d)G + (k + xd)G \\ &= x(pG) + kG \\ &= xO + kG \\ &= kG \end{split} \end{equation} is public too. Given \(x \ne 0\), knowing \(k\) immediately reveals the secret key \(d = ((k + xd) - k)x^{-1}\) with a extended euclidean algorithm, in \(O(\log p)\). Therefore, given a valid signature, recovering \(d\) can be reduced to recovering \(k\) from the publicly computable point \(R = kG\), if we assume its harder than \(O(\log p)\) (which it normally is).
So... It's not increased. Recovering \(k\) from \(kG\) is the same kind of problem as recovering \(d\) from the public key \(E = (p-d)G\), and these are called the discrete logarithm problem (DLP).
That said, a valid Schnorr signature exposes another DLP instance, \(R=kG\), but does not provide a known shortcut for recovering the secret key beyond solving the DLP in the underlying group.
A verification is derived from the above arithmetic around \(R\). Given public key \(E\), message \(M\) and signature \((x, s)\), take \(R = xE + sG\). If \(H(R||M) = x\), the signature is valid.
Why? If it is valid, \(R = kG\) and \(x = H(kG||M)\), which is cryptographically equivalent to \(H(R||M) = H(kG||M) = x\) since \(H\) is a cryptographic hash function.
Note that if same \(k\) is used for two different messages and the attacker can know that (i.e. it is not random), subtracting them: \[ (k + x_1d) - (k + x_2d) = (x_1 - x_2)d \] makes \(d\) is determined by \((x_1 - x_2)^{-1}(x_1 - x_2)d\) in \(O(\log p)\).
As seen above, recovering the secret key reduces to solving the DLP.
For a group of order \(N = p_1^{e_1}\cdots p_n^{e_n}\), the Pohlig–Hellman algorithm reduces a DLP in the whole group to DLPs in subgroups of order \(p_i^{e_i}\). Solving each subgroup independently with generic DLP algorithm like Pollard's rho yields an overall time complexity \[O(\Sigma e_i(\log N + \sqrt{p_i})).\]
It becomes \(O(\sqrt{N})\) if \(N\) is a prime. This is why Schnorr signatures are instantiated over prime-order groups.
Pohlig-Hellman with Pollard's rho solves DLP for an arbitrary group, but faster algorithms may exist for a specific group.
The most immediate example is the field \(\mathbb Z/p\mathbb Z\) itself. Viewed only as an additive group \((\mathbb Z/p\mathbb Z, +)\), scalar multiplication is simply field multiplication.
Hence, for any nonzero \(g\), \[d = g^{-1}(dg),\] which can be evaluated using the extended euclidean algorithm in \(O(\log p)\).
This means that if we create a 256-bit key (meaning \(p\) is a large prime close to \(2^{256}\)), the private key can be obtained from the public key in only a few hundred arithmetic operations. Therefore, although \((\mathbb Z/p\mathbb Z, +)\) is a prime-order cyclic group, it must not be used for Schnorr signatures.
On the other hand, if we choose an elliptic curve group, like secp256k1 on Taproot, as \(C\), no faster algorithm is known. That said, about \(2^{128}\) group operations are needed for same thing.
We have seen that recovering the secret key is computationally equivalent to solving the DLP in the underlying group.
However, as one would expect from a secure public-key signature algorithm, the Schnorr scheme guarantees more than just key secrecy.
Pointcheval and Stern proved that forging a signature from public values directly reduces to solving the DLP. The actual proof is beyond the scope of this post, but you can find it in Theorem 13 of their 1996 paper (PDF) if you want to dig deeper.
Thank you for reading! Please mail me at [email protected] for a comment.
Copyright 2026 Hee-Suk Kim