Problem 1. (25 points) Let p be a prime and g be a generator of the multiplicative group Z∗p of integers modulo p, (note that F∗p is also commonly used to denote this group, but we will stick with Z∗p). Let λ be the bit length of p. Show that the Decisional Diffie-Hellman assumption does not hold in this group. Specifically, design an algorithm A that runs in time t = O(λ3) and distinguishes LZ∗p from LZ∗p with advantage ε = 1/4 (see Definition 4.4). Hint: A is able to test, in time O(λ3) whether values are squares modulo p — but you have to explain how and why that helps.
Problem 2. (15 points) Let G be a group with a generator g and order n. Let λ be the bit length of n. Show that if you have the discrete logarithm of some h1 ∈ G and h2 ∈ G, then you can efficiently (i.e., in time polynomial in λ) compute the discrete logarithms h1h2 and h1/h2.
Problem 3. (60 points) Again, let G be a group with a generator g and order n. Let λ be the bit length of n; assume group operations take time that is polynomial in λ. Suppose you have an algorithm F0 that runs in time t and computes discrete logarithms for 1% of G: that is, there is a subset H ⊂ G of size n/100 such that if h ∈ H, F0(h) produces logg h. For the remaining 99% of inputs, F0 outputs “fail�.
(a) (30 points) Design an algorithm F1 that runs time t+poly(λ) and outputs the discrete logarithm of its input h with probability at least 1% for every h ∈ G. The difference between F0 and F1 is that F0 works always for some inputs, while F1 will work sometimes for all inputs. Hint: re-randomize h, then use F0. The previous problem will be useful.
(b) (30 points) Now design an algorithm F2 that runs time 500t + poly(λ) and outputs the discrete logarithm of its input h with probability at least 99% for every h ∈ G.
2 answers
1)
Experiment Expddh-1(A) G,g
x←$Zm y←$Zm
z←xymodm
X←gx;Y ←gy;Z←gz d←A(X,Y,Z)
Advddh(A) = Pr Expddh-1(A) = 1 − Pr Expddh-0(A) = 1
2)
Experiment Expdl (A) G,g
x ←$ Z m ; X ← g x
x ← A(X)
If gx = X then return 1 else return 0
Advdl (A) = Pr Expdl (A) = 1
3)
Algorithm Km$ od
l1 ← ⌊k/2⌋ ; l2 ← ⌈k/2⌉ Repeat
p←$ {2l1−1,...,2l1 −1}; q←$ {2l2−1,...,2l2 −1}
3a)
Until the following conditions are all true:
– TEST-PRIME(p) = 1 and TEST-PRIME(q) = 1 – p̸=q
– 2k−1≤N
N ← pq
Return (N, e), (N, p, q, d)
3b)
Algorithm Kresa Repeat
( N , p , q ) ←$ K m$ o d ( k ) Until
– e<(p−1)ande<(q−1)
– gcd(e,(p − 1)) = gcd(e,(q − 1)) = 1
M ←(p−1)(q−1)
Compute d by running the algorithm of Proposition 10.3.3 on inputs M, e Return ((N, e), (N, p, q, d))