Prove the Security of Schnorr's Signature Scheme

Question

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!

Answer 1

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.

Answer 2

As an alternative to @Occams_Trimmer's helpful answer:

A perhaps simpler proof of this fact can be gotten by combining Theorems 12.10 and 12.11 of Katz and Lindell's book.

These authors first give a generic Fiat–Shamir transform for 3-move protocols. It then remains only to show that the interactive Schnorr "identification scheme" is secure, which is much easier to do. To summarize:

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.

Please see Katz and Lindell for proofs, as well as definitions, e.g., of what it means for an "identification scheme" to be "secure".