FC08 Assignment 2

From Theory

Back to CS 8803FC - Foundations of Cryptography. Spring 2008.

1 Problem 1: One-way functions.
2 Problem 2: Averaging argument.
3 Problem 3: Number Theory.
4 Problem 4: Computational and statistical indistinguishability.

Problem 1: One-way functions.

Let $f_{mult}:\{0,1\}^*\rightarrow\{0,1\}^*$ be the function defined by $f_{mult}(x,y)= x\cdot y$ .

(1) Prove that assuming the factoring assumption is true, $f m u l t$ is a weak one-way function. (Hint: Use Chevyshev's Theorem on density of primes).

(2) Use the weak one-way function $f m u l t$ to construct a strong one-way function. Prove that your construction satisfies the definition of strong one-wayness without referencing the general hardness amplification theorem.

[edit]

Problem 2: Averaging argument.

Let $A$ be a (possibly probabilistic) algorithm, and let $f:\{0,1\}^*\rightarrow\{0,1\}^*$ be a function. Suppose that there exists $\alpha(\cdot)$ such that for every $n\in N$ ,

$Pr[A(x)=f(x)]\geq \alpha(n)$ , where the probability is over $x\in_R \{0,1\}^n$ and over the random coin tosses of $A$ .

For any $\epsilon(\cdot)$ and for any $n \in N$ , let $S_n=\{x\in\{0,1\}^n: Pr [A(x)=f(x)]\geq \alpha(n)-\epsilon(n)\}$ , where the probability is over the random coin tosses of $A$ .

Prove that $Pr[x\in S_n] \geq \epsilon(n)$ , where the probability is over $x\in_R \{0,1\}^n$ .

[edit]

Problem 3: Number Theory.

(1) The Diffie-Hellman problem is as follows: Given input $(p, q, g, g x, g y)$ where $p$ is a safe prime, i.e. $p$ is a prime of the form $2 q + 1$ where $q$ is prime, $g$ is a generator of a subgroup of order $q$ in $Z p$ , and $x,y \in Z_q$ compute the element $g x y mod p$ .

The Square problem is as follows: Given input $(p, q, g, g x)$ where $p$ is a safe prime , i.e. $p$ is a prime of the form $2 q + 1$ where $q$ is prime, $g$ is a generator of a subgroup of order $q$ in $Z p$ , and $x \in Z_q$ , compute the element $g^{x^2} \bmod p$ .

Show that the Diffie-Hellman and the Square problem are polynomial-time equivalent. In other words, show that an algorithm that solves the Square problem can be used to solve the Diffie-Hellman problem (with at most a polynomial amount of extra work) and vice-versa.

(2) Suppose $p > 2$ is a prime and $g$ and $h$ are both generators of $Z_p^*$ . Prove or disprove the following statements:

A: $\{g^x \bmod p\}_{x\leftarrow Z_p^*} = \{g^{xy} \bmod p\}_{x,y \leftarrow Z_p^*}$

B: $\{g^x \bmod p\}_{x\leftarrow Z_p^*} = \{h^x \bmod p\}_{x\leftarrow Z_p^*}$

C: $\{g^x \bmod p\}_{x\leftarrow Z_p^*} = \{x^g \bmod p\}_{x\leftarrow Z_p^*}$

D: $\{x^g \bmod p\}_{x\leftarrow Z_p^*} = \{x^{gh} \bmod p\}_{x\leftarrow Z_p^*}$

(Recall that $\{g^x \bmod p\}_{x\leftarrow Z_p^*}$ is a probability distribution. To show that two distributions are identical prove that each of member of one distribution occurs with same probability in both the distribution. To show they are not identical, give a counter example, by finding a member in one distribution, which occurs with different probability in the two distributions.)

[edit]

Problem 4: Computational and statistical indistinguishability.

Two distribution ensembles ${X n},{Y n}$ are statistically close if their statistical difference is negligible, where their statistical difference is defined as

$\delta(n)=\frac12\sum_\alpha|Pr[X_n=\alpha]-Pr[Y_n=\alpha]|$ .

(1) Prove that ${X n},{Y n}$ are statistically close if and only if for every set $S\subseteq \{0,1\}^*$ ,

$\delta_S(n)= |Pr[X_n\in S]-Pr[Y_n\in S]|$

is negligible in n.

(Hint: Prove that the statistical difference between $X n, Y n$ equals $max S {δ S (n)})$ .

(2) Prove that if two ensebmles are statistically close then they are computationally indistinguishable.

(3) Let ${X n},{X n'},{Y n},{Y n'}$ be four distribution ensembles such that $\{X_n\}\approx\{Y_n\}$ and $\{X_n'\}\approx\{Y_n'\}$ , where $\approx$ denotes computational indistinguishability. Prove that $\{X_n\circ X_n'\}\approx\{Y_n\circ Y_n'\}$ .