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

( p − 1 θ − 1 ) trials we can find with high probability

This lemma means that within

d for

a successful leaf ), i.e. a subtree in which

random leaves are successful with a fixed distinguished ancestor

λ such that f ( ν ) > (1 − θ ) p / ν = dist( λ

ν with probability at

d .

least (1 − θ ) p /

d .Wehave

Proof. We let G be the set of all good nodes ν such that f ( ν ) > (1 − θ ) p /

Pr[dist( λ ) ∈ G | succ( λ )] = Pr[dist( λ ) = ν | succ( λ )] .

ν ∈ G

Since visit( ν ) is included in dist( λ ) = ν ,wehave

)] Pr[succ(

λ ) and dist( λ ) = ν | visit( ν )]

Pr[dist( λ ) = ν | succ( λ )] = Pr[visit( ν

Pr[succ( λ )]

f ( )

p .

ν

= Pr[visit( ν )]

Hence

− θ
d

1

λ ∈ | λ ≤ ν

Pr[dist( ) G succ( )] Pr[visit( )]

ν ∈ G

1 − θ

d

≤ ν .

Pr[visit( )]

ν

d ,

The last sum is equal to thus Pr[dist( λ ) ∈ G | succ( λ )] ≤ 1 − θ . We deduce

Pr[dist( λ ) ∈ G | succ( λ )] ≥ θ .

10.5 Exercises

Exercise 10.1. Show that if we can compute the discrete logarithm of y in the subgroup
of Z p spanned by g, then we can break the ElGamal signature, the Schnorr signature,
and the DSA signature.

Exercise 10.2. Prove that for some pair of two messages M and M ,q

= H ( M ) −

H ( M ) is a valid prime which can lead to some ( p

g ) DSA public parameters. In
this case, prove that any signature of M is also a valid signature of M . 2

, q ,

Exercise 10.3. In the DSA signature scheme, show that if we can invert the k →

( g k

mod p ) mod q function, then we can break the scheme.

2

This exercise was inspired by Ref. [180].