Digital Signature - A Classical Introduction to Cryptography: Applications for Communications Security - page 264

pseudorandom generator fed with the previous communications and the message to
be signed.

10.4.2 Security in the Random Oracle Model

A further step forward to formal proofs of security was made by Jacques Stern and David
Pointcheval. They formally proved the security of the ElGamal signature scheme in what
is called the “random oracle model”, demonstrating that it is hard for an adversary to
existentially forge signatures, even with an access to the signing oracle. Note that this
proof holds on average over the public parameter choice (i.e. the value of p and g )
and not for any choice. As a matter of fact, the result by Pointcheval and Stern was
presented at the same conference where the attack of Bleichenbacher was presented.
(The latter indeed demonstrates that for some choices of p and g it is indeed very easy
to forge a signature.) (See Refs. [33, 146]).

This proof technique was later adapted to other signature schemes. It also motivated
the Pointcheval-Vaudenay one for which the proof argument works better and for any
choice of public parameters. We provide here this demonstration.

The security proof relies on the assumption that the underlying hash function H
is replaced by a truly random oracle. This is not a practical model but an idealized
approximation of what happens in practice.

Let us formalize the Pointcheval-Vaudenay scheme with a random oracle by the
following three algorithms.

→ , , , ,

Setup ( p q g y x ): generate two prime numbers p and g such that q divides

1, an integer g which spans a subgroup of Z p of order q . Pick a secret
key x

−

p

∈ Z q . Compute the public key y = g x mod p .

∈ Z q , compute r Sig( M ) → ( h , r , s ): pick a random k = ( g k mod p ) mod q ,

query the oracle with r || M and obtain h = H ( r || M ), and compute s =

h + xr
k

mod q , the signature is σ = ( h , r , s ).

Ver( M , h , r , s ): query the oracle with r || M and check that h = H ( r || M ) and r =

g s mod q y s mod q

mod p mod q .

We will prove the following theorem.

Theorem 10.2. We consider the three algorithms Setup, Sig, and Ver as defined above.
We assume that the oracle H in the above algorithms is a random oracle which outputs
elements of Z q .Welet ( g k

− 1 denote the largest preimage set size for the k → mod

p ) mod q mapping from Z q to Z q . Let

ε , T , and Q be arbitrary positive real numbers

Q 2

such that ε / q. We say that A is a ( ε, Q , T ) -adversary if it is an algorithm

which, given the output ( p y ) from Setup, can query Sig or H at most Q times

and output within a time less than T a ( M

, q , g ,

s ) quadruplet such that M was never
queried to Sig, and that the probability that Ver accepts the quadruplet is greater

, h , r ,