## Description

Ex. 1 — Lamport one-time signature scheme

1. Describe the Lamport signature scheme.

2. Highlight the benefits and drawbacks of this method.

3. Explain how this scheme can be attacked is a same key is used to sign more than one message.

4. What is a Merkle tree, and how can it be used to improve the efficiency of the Lamport one-time

signature scheme?

Ex. 2 — Chaum-van Antwerpen signatures

In the lectures we presented the concept of undeniable signatures but we did not prove any of the results.

We now do it, reusing the same notations.

1. In this question we want to prove that if s 6≡ mx mod p, then s will be accepted as a valid signature

with probability less than 1/q.

a) For each value r Alice generates, how many ordered pairs he1, e2i can be considered?

b) Writing r = α

i

, t = α

j

, m = α

k

, and s = α

l

, i, j, k, l ∈ Z/qZ, consider the system of

congruences

r ≡ s

e1β

e2 mod p

t ≡ me1α

e2 mod p,

and prove it has a unique solution.

c) Conclude on the probability that Alice accepts an invalid signature.

2. We now prove that if s 6≡ mx mod p, and the disavowal protocol is respected then we should have

t1α

−e2

f1 ≡

t2α

−f2

e1

mod p.

a) Prove that

t1α

−e2

f1

≡ s

e1f1x

−1

mod p.

b) Applying the same method to

t2α

−f2

e1

mod p conclude that Bob can convince Alice that

an invalid signature is a forgery.

3. We finally prove that if s ≡ mx mod p, but t1 6≡ me1α

e2 and t2 6≡ mf1α

f2

, then

t1α

−e2

f1

6≡

t2α

−f2

e1

mod p with probability 1 − 1/q.

a) Prove this result by contradiction using question 1.

b) Does this result require Bob to follow the disavowal protocol?

c) Can Bob convince Alice that a valid signature is a forger

Ex. 3 — Simple questions

1. DSA with the parameters q = 101, p = 7879, α = 170, x = 75, and β = 4567 is used to signed

a message whose hash is 52.

a) Determine the signature of the message if k = 49.

b) Verify the signature.

2. Bob used the Elgamal signature scheme to sign his messages m1 = 8990 and m2 = 31415. He

got hm1, 23972, 31396i, and hm2, 23972.20481i. Knowing his public parameters are p = 31847,

α = 5, and β = 25703, recover both the random value k and his private key x.