Prove the Security of Schnorr's Signature Scheme

I know that Schnorr's signature is important since it is one of the most compact signature schemes whose security has been proved in the random oracle model.

Now, I want to know if such proof is easy and someone could explain it to me, or maybe just point out the main steps of the proof.

For the sake of clarity, the Schnorr's signature scheme I know is the one presented by the Wikipedia page Schnorr signature:

• Choosing the parameter: all users of the scheme agree on a group $G$ of prime order $q$, in which the DLP is hard (e.g. $G$ is a Schnorr Group, or an Elliptic Curve of prime ordere $q$), a generator $g \in G$, and on a hash function $H:\{ 0,1 \}^* \rightarrow \mathbb{Z}_q$
• Key generation: the signer chooses a secret key $x \in \mathbb{Z}_q$ and makes $y=g^x$ public.
• Signing: to sign a message $M$, the signer chooses a random $k \in \mathbb{Z}_q - \{ 0 \}$, computes $r=g^k$, lets $e=H(M||r)$, and lets $s=k-xe$. The signed message is $(M,(s,e))$.
• Verifying: anyone can verify that $(s,e)$ is a signature on $M$ by computing $r_v = g^s y^e$ and $e_v = H(r_v||M)$; if $e_v = e$ the signature is verified.

Now, the proof of correctness is quite straightforward (i.e. if one follows the protocol, then the verification equation $e_v = e$ holds), but I don't see how to formally prove the security (i.e. if one doesn't follow the protocol, it is very unlikely that the verification equation will hold, hence it is hard to forge a signature on a message without knowing the secret key).

Any hint or suggested readings will be appreciated!

• That description is not quite Schnorr's signature scheme as published (see reference and description in this question). Main difference is that in Schnorr's article the hash $H$ has narrow output (about half the bitsize of $q$). Also the minus sign is applied to $x$ during computation of the public key, so that $s=k+xe\bmod q$ (that trivially does not matter to security). And the notations differ. I wish I knew the origin of the variant in this question, Wikipedia, and the HAC 11.5.3. – fgrieu Jun 25 '17 at 18:04
• Usually one doesn't proof this directly on the signature scheme. Instead, prove properties of the underlying identification scheme, and then use Fiat-Shamir to get a secure signature scheme. The property you are looking for is soundness, and the proof technique is called rewinding (which may be a bit unintuitive). Perhaps have a look at web.stanford.edu/class/cs259c/lectures/schnorr.pdf. – CurveEnthusiast Jun 25 '17 at 23:55
• As mentioned above, the security is argued using the rewinding technique and the success probability is then bounded using a forking lemma. You should read Chapter 3 here for a detailed (and intuitive) explanation. – Occams_Trimmer Jun 26 '17 at 14:06

Pointcheval and Stern [PS00] proved that the Schnorr signature is existentially unforgeable under chosen-message attacks (EU-CMA) in the random oracle model assuming that the discrete-logarithm problem$^1$ (DLP) is hard.

On a high level, the reduction (from DLP to the EU-CMA-security of Schnorr signature) works as follows. The reduction algorithm $\mathcal{B}$ embeds its DLP challenge $g^\alpha$ into the public key (i.e., sets $y=g^\alpha$) and then uses the oracle-replay attack to obtain, from the forger $\mathcal{F}$, two different forgeries that share the signing randomness ($r=g^k$). This enables $\mathcal{B}$ to solve for $\alpha$.

For simplicity, let's first focus on a weaker model called the existential forgery under no-message attacks (EU-NMA) and a strong forger that is always successful. We show that a strong forger $\mathcal{F}$ that breaks the Schnorr signature in the EU-NMA model making at most $q$ queries to the random oracle $H$ (i.e., a $(1,q)$-adversary) can be used to break the DLP with probability $1/q$.

This requires two rounds of simulation:

1. Round 1. $\mathcal{B}$ runs $\mathcal{F}$ on $(G,g,g^\alpha)$; the random oracle $H$ is simulated in the standard manner (i.e., lazy sampling plus a table to ensure consistency). At the end of this round $\mathcal{F}$ returns a forgery $(M_0^*,(s_0^*,e_0^*))$ where $e_0^*=H(M_0^*\|r_0^*)$. For simplicity, it is assumed that $\mathcal{F}$ made the random oracle query $H(M_0^*\|r_0^*)$.
2. Rounds 2. Now $\mathcal{B}$ rewinds $\mathcal{F}$ to the point where it made the random oracle query $H(M_0^*\|r_0^*)$ in Round 1 (the "critical" point) and re-runs $\mathcal{F}$ but answering the fresh random oracle queries independent of the previous round.$^2$ This constitutes the oracle-replay attack. At the end of Round 2, $\mathcal{F}$ returns a forgery $(M_1^*,(s_1^*,e_1^*))$ where $e_1^*=H(M_1^*\|r_1^*)$.

There is a non-negligible probability (at least $1/q$, but this has to be argued rigorously) that in Round 2 too $\mathcal{F}$ forges at the critical point (i.e., $M_1^*=M_0^*$ and $r_1^*=r_0^*$) but that the responses to the random oracle query $H(M_0^*\|r_0^*)$ were different (i.e., $e_1^*\neq e_0^*$). The intuitive reason is that $\mathcal{F}$ has to forge on some query, and in the worst case it chooses this point randomly. If this is indeed the case, then $$s_0^*=k_0^*-\alpha e_0^* \text{ and } s_1^*=k_0^*-\alpha e_1^*,$$ (as $r_1^*=r_0^*$, but $e_1^*\neq e_0^*$) and $\mathcal{B}$ can solve for $\alpha$ $$\alpha=\frac{s_1^*-s_0^*}{e_0^*-e_1^*}.$$

The above argument can be strengthened to accommodate a general $(\epsilon,q)$-adversary in the EU-CMA model. To simulate the signing oracle (for the EU-CMA model) the reduction only has to program the random oracle appropriately.$^3$. Bounding the success probability of the reduction for the general adversary (that is successful with a non-negligible probability $\epsilon$) is quite technical and uses the so-called forking lemma. To be precise, it is shown in [PS00] that an $(\epsilon,q)$-forger $\mathcal{F}$ that breaks the Schnorr signature in the EU-CMA model can be used to break the DLP with probability $O(\epsilon^2/q)$.$^4$

Footnotes.

$^1$The DLP on a cyclic group $(G,g,q)$ requires finding $\alpha\in\mathbb{Z}_q$ given $g^\alpha\in G$.

$^2$That is, the queries up to the critical point are answered consistently, but the fresh queries after the critical point are answered independently of Round 1.

$^3$To generate a signature for a message $M$, select $e,k\in_R\mathbb{Z}_q$, set $r=(g^\alpha)^e\cdot g^k$, and program the random oracle to set $H(M\|r)=e$. Return $(M,(e,k))$ as the signature. It is not difficult to see that the message is valid, and from the right distribution.

$^4$It was later shown in a series of works [PV05,GBL08,Seu12] that the loss is tightness of $\epsilon/q$ is inherent (conditioned on the assumption that the so-called one-more discrete-logarithm is hard).

References.

[PS00] David Pointcheval and Jacques Stern. Security arguments for digital signatures and blind signatures. Journal of Cryptology, 2000.

[PV05] Pascal Paillier and Damien Vergnaud. Discrete-Log-Based Signatures May Not Be Equivalent to Discrete-Log. ASIACRYPT 2005.

[GBL08] Sanjam Garg, Raghav Bhaskar, and Satyanarayana V. Lokam. Improved Bounds on Security Reductions for Discrete-Log Based Signatures. CRYPTO 2008.

[Seu12] Yannich Seurin. On the Exact Security of Schnorr-Type Signatures in the Random Oracle Model. EUROCRYPT 2012.

• Thank you for your useful answer. One question: You wrote "making at most q queries to the random oracle H (i.e., a (1,q)-adversary) can be used to break the DLP with probability 1/q"; this seems to imply that the less queries I make to the oracle H, the highest the probability of breaking the DLP. How is that possible? I can't solve this doubt – richard Aug 21 '17 at 13:11
• That's correct: the fewer query the adversary makes to the random oracle the better the bound is. To see this, let's consider the extreme case where the adversary can make only one query. Here, the adversary has to forge on this query in both the rounds, and therefore the reduction knows exactly where to "fork". But more query the adversary is allowed, the more freedom it has to choose which query to forge on making the reduction's life harder. – Occams_Trimmer Aug 21 '17 at 14:49
• There is a fundamental issue I don't understand with this proof: Why is it the simulator's prerogative to simulate the RO? I mean, as far as I understand, the function acting as RO is external and picked independently from the forger, making this whole mechanism of extracting discrete log fail. Any chance you could clear that up? I'm pretty lost here. Thanks! – Chipotle May 27 '19 at 15:09
• Long story short, this is the only way that we currently know to prove security of Schnorr signatures and there is evidence that this is inherent: see eprint.iacr.org/2013/140 and the references therein. – Occams_Trimmer May 30 '19 at 12:28

Theorem 12.10 ([KL15]). Let $$\Pi$$ be a be an identification scheme, and let $$\Pi'$$ be the signature scheme that results by applying the Fiat–Shamir transform to it. If $$\Pi$$ is secure and $$H$$ is modeled as a random oracle, then $$\Pi'$$ is secure.
Theorem 12.11 ([KL15]). If the discrete-logarithm problem is hard relative to $$\mathcal{G}$$, then the Schnorr identification scheme is secure.