VE475 Introduction to Cryptography Homework 8 Solved

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 Merkie 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 ifs ≢ mx mod p, then swill be accepted as a valid signature with probability less than 1/q.

a)  For each value r Alice generates, how many ordered pairs ⟨e1, e2⟩ 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 ≡ se1β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 ≢ 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 ≡ se1f1x−1 mod p.

b)   Applying the same method to (t2α−f)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 ≢ me1αe2 and t2 ≢ mf1αf2, then (t1α−e2)f1 ≢ (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 forgery?

Ex. 3 - Simple questions

1. DSA with the parameters q = 101, p = 7879, a = 170, x = 75, and 3 = 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 ⟨m1, 23972, 31396), and (m2,23972.20481). Knowing his public parameters are p = 31847, a = 5, and 0 = 25703, recover both the random value k and his private key x.