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.

Question

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.

Answer 1

We do not do your homework for you. Although it might take more effort to do the work on your own, you will profit more from your effort. We will be happy to evaluate your work though.

Answer 2

Now, PsyDag. Could you evaluate it?

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))