Security of Schnorr Signature in AGM

The Schnorr Signature Scheme

EUF-CMA Game

Security of Schnorr Signatures in the AGM

Theorem: Let  be a group generator. Let  be an algebraic adversary against the  -CMA security of the Schnorr signature scheme Sch[GrGen] running in time at most and making at most  signature queries and  queries to the random oracle. Then there exists an algorithm  solving the  problem w.r.t. GrGen, running in time at most  such that

: Let  be an algebraic adversary in EUF-CMA  that makes at most  signature queries and  RO queries. We proceed by a sequence of games specified in Figure below:

The dark-gray comments show how  solves DL.

Game0

The first game is EUF-CMA for the Schnorr signature scheme with a random oracle . The game maintains a list  of queried messages and  of values sampled for . Since the adversary is algebraic, it must provide a representation  for its forgery  such that  and similarly for each RO query .

To prepare the change to , we have written the finalization of the game in an equivalent way: it first checks that  and then runs , which we have written explicitly.

Also, the game calls  rather than  but in  these two oracles are equivalent.

By definition,

Game1

In , when  is called, the game returns 0 in case the freshly drawn random value  satisfies  .

Clearly, for each call to  this happens with probability  Since  is called at most times by the adversary and once by the game when checking the signature, by the union bound, one has

Game2

In the final game we use the standard method for Schnorr signatures of simulating the SIGN oracle without the secret key  by programming the random oracle.

 and  are identical unless  returns 0 in line (II). For each signature query,  is uniformly random, and the size of table  is at most , hence the game aborts in line (II) with probability at most  By summing over the at most  signature queries, we have

Reduction to DL

We now construct an adversary  solving DL with the same probability as  wins .

On input group description  and  the adversary runs  on input  and simulates , which can be done without knowledge of . It also uses an auxiliary table that for each query  stores the representation  of . Assume that the adversary wins  by returning  and let  (which is necessarily defined after the call  We argue that necessarily  and

First note that  as otherwise the game would already have returned  Hence  can only have been defined either (1) during a call to  by the adversary or  if it is still undefined when  stops, by the game when calling  In both cases, this call sets both and  and  is necessarily satisfied as otherwise the game would have returned 0 at line (I).

Since  with  and validity of the forgery implies that  it follows that  and  can compute

We thus have

Assuming that scalar multiplications in  and assignments in tables  and  take unit time, the running time of  is .