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.
