Hello, if you have any need, please feel free to consult us, this is my wechat: wx91due
CS276: Cryptography Problem Set 1
Problem 1
Assume that f is a length preserving one-way function, i.e., for every x ∈ {0, 1} ∗ it holds that |f(x)| = |x|. For each of the following functions g, prove that g is a one-way function, or provide a counterexample to demonstrate that it is not.
A: g(x) = f(f(x))
B: g(x) = f(¯x)
C: g(x) = f(x) ⊕ x
D: g(x, y) = f(x ⊕ y)
E: g(x) = f(x)|f(¯x)
(Note that x¯ denotes the bitwise complement of x and | denotes concatenation, e.g., 1011|1011 = 10110100.)
Problem 2
Let p be a prime and let g and h be (not necessarily distinct) generators of Z ∗ p . Prove or disprove the following statements:
A: {x ← Z ∗ p : g x mod p} = {x ← Z ∗ p ; y ← Z ∗ p : g xy mod p}
B: {x ← Z ∗ p : g x mod p} = {x ← Z ∗ p : h x mod p}
C: {x ← Z ∗ p : g x mod p} = {x ← Z ∗ p : x g mod p}
D: {x ← Z ∗ p : x g mod p} = {x ← Z ∗ p : x gh mod p}
(Recall that {x ← Z ∗ p : g x mod p} is a probability distribution. You are being asked to prove or disprove the statement that two probability distributions are identical.)
Problem 3
Suppose that, in a moment of great insight, you discovered a polynomial-time algorithm A that solves the Discrete Logarithm Problem in a special case. Namely on inputs p, g, and g x mod p, the algorithm A outputs x if p is a prime, g is a generator of Z ∗ p and g x mod p is prime.
Show that there exists a probabilistic polynomial-time algorithm B that solves any instance of the Discrete Logarithm Problem.
Problem 4
In this problem, we study how to efficiently sample generators modulo a prime.
Let p be a prime. The group Z ∗ p can be shown to be cyclic of order p − 1; in fact, while proving this, one also obtains the fact that the number of elements of order p − 1 in Z ∗ p (i.e., the number of generators in Z ∗ p ) is equal to φ(p − 1). Since φ(n) = Θ(n/ log log n), the quantity φ(p − 1)/p − 1 is non-negligible. In particular, by choosing an element g of Z ∗ p at random, the probability that g is a generator of Z ∗ p is non-negligible. However, given an element g in Z ∗ p , how can we decide if it is a generator or not?
Describe a polynomial-time algorithm that, on input an element g ∈ Z ∗ p , an odd prime p, and the factorization of p − 1, decides whether g is a generator of Z ∗ p .
(Note: Efficiently sampling generators modulo a prime is sometimes needed in practice, such as in Elgamal’s public-key cryptosystem. But, how does one obtain the factorization of p − 1? Usually, one generates the prime p along with the factorization of p−1. For example, in Elgamal’s public-key cryptosystem a prime p is chosen to have the form p = 2q + 1 for some prime q, so that p − 1 = 2q; a prime of this form is called a safe prime.)
Problem 5
Give a strategy to distinguish between (g x , gy , gxy) mod p and (g x , gy , gr ) mod p with non-negligible advantage, where x, y, r are chosen at random such that 1 ≤ x, y, r ≤ p − 1, and g is a generator of Z ∗ p .