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.
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.
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))
To solve these problems, knowledge of basic concepts in cryptography, mathematical groups, and computational complexity is required. Below are the step-by-step explanations for each problem.
Problem 1:
The goal is to design an algorithm A that can distinguish between two groups Z∗p and Z∗p, given a prime p and a generator g, with an advantage of 1/4.
To solve this problem, we first need to understand the Decisional Diffie-Hellman assumption and how it applies to this group.
1. Decisional Diffie-Hellman (DDH) Assumption:
The DDH assumption states that given three elements (g, g^a, g^b) in a group G, it is computationally difficult to determine whether g^ab or a random group element was given in the triplet.
To design algorithm A, we can take advantage of the fact that we can test, in time O(λ^3), whether values are squares modulo p.
2. Designing Algorithm A:
The algorithm A works as follows:
- Choose random values a and b from {1, 2, ..., p-1}.
- Compute h1 = g^a and h2 = g^b.
- Choose a random value r from {1, 2, ..., p-1}.
- Compute h3 = g^(ar^2).
- If h3 is a square modulo p, output 1 (indicating it is LZ∗p).
- If h3 is not a square modulo p, output 0 (indicating it is not LZ∗p).
3. Explanation of Algorithm A:
- If g^ar^2 is in the group Z∗p, it can be written as (g^a)^r^2 = h1^r^2.
- Thus, h3 will be a square modulo p if h1 is a square modulo p.
- If h1 is not a square modulo p, then h3 will not be a square modulo p.
By choosing r randomly, we make it very unlikely that h3 will be a square modulo p if h1 is not a square modulo p. Hence, algorithm A has a 1/4 advantage in distinguishing between LZ∗p and LZ∗p.
Problem 2:
The goal is to show that given the discrete logarithms of h1 and h2, we can efficiently compute the discrete logarithms of h1h2 and h1/h2.
To solve this problem, we need to understand the properties of the discrete logarithm and group operations.
1. Properties of Discrete Logarithm:
Given a group G with generator g, and discrete logarithms x = logg(h1) and y = logg(h2), we want to compute the discrete logarithms of h1h2 and h1/h2.
2. Computing the Discrete Logarithm of h1h2:
- Compute h3 = h1h2.
- Compute the discrete logarithm x3 = logg(h3).
- Since h3 = h1h2 = g^(x1 + x2), x3 = x1 + x2.
Therefore, we can efficiently compute the discrete logarithm of h1h2 by simply adding the discrete logarithms of h1 and h2.
3. Computing the Discrete Logarithm of h1/h2:
- Compute h4 = h1/h2.
- Compute the discrete logarithm x4 = logg(h4).
- Since h4 = h1/h2 = g^(x1 - x2), x4 = x1 - x2.
Similarly, we can efficiently compute the discrete logarithm of h1/h2 by subtracting the discrete logarithm of h2 from the discrete logarithm of h1.
Problem 3:
The goal is to design two algorithms F1 and F2 that can compute the discrete logarithm for elements in a group G.
To solve this problem, we need to use the provided algorithm F0 and design F1 first, then use F1 to design F2.
(a) Designing Algorithm F1:
The algorithm F1 works as follows:
- For the given input h in G:
- Choose a random value x from {1, 2, ..., n-1}.
- Compute h1 = hx.
- Run algorithm F0 on h1 and get the result y = F0(h1).
- Compute the inverse x^-1 of x modulo n.
- Return y*x^-1.
The probability that F1 outputs the discrete logarithm of h is at least 1% for every h in G because F0 outputs the correct result for 1% of the elements in G.
(b) Designing Algorithm F2:
The algorithm F2 works as follows:
- For the given input h in G:
- Run algorithm F1 on h to compute the discrete logarithm y1.
- Repeat the following 500 times:
- Choose a random value x from {1, 2, ..., n-1}.
- Compute h1 = hx.
- Run algorithm F1 on h1 to compute the discrete logarithm y2.
- If y2 is not equal to y1, break the loop.
- If the loop completes without breaking, return y1 as the output.
By repeating the process 500 times, the probability that F2 outputs the correct discrete logarithm for h is increased to at least 99% for every h in G.
Note: This explanation assumes a basic understanding of cryptographic concepts and group operations. It is recommended to refer to appropriate textbooks or materials for a more detailed explanation.