Course:Fall 2006 Exercises 3

From CRYPTUTOR

Jump to: navigation, search

This is the third set of exercise problems for the Fall 2006 introductory course.

The problems will be finalized by Wednesday, October 4. The solutions are due in class on Friday, October 13.

Exercises on pseudorandom permutations, DDH assumption and public-key encryption

Optimality of the Luby-Rackoff Feistel Network In class it was mentioned that the three-layer Luby-Rackoff network (i.e., a Feistel network with a pseudorandom function as the round function) is a pseudorandom permutation.
1. [15 points] Show that no matter what the round function is, a single-layer Feistel network is not a pseudorandom permutation.
2. [15 points] Show that a two-layer Feistel network is not a pseudorandom permutation either, no matter what the two round functions are. Show this by giving two queries you would make to an oracle to tell if the oracle is a truly random permutation or one implemented using a two-layer Feistel network. (The second query can depend on the answer to the first query.)
3. (Extra Credit) Recall that a four-layer Luby-Rackoff network is a strong pseudorandom permutation. Show that no matter what round functions are used, a three-layer Feistel network is not a strong pseudorandom permutation. Remember that in your attack, you can use queries to the permutation oracle and its inverse permutation.
DDH Assumption Suppose is a cyclic group with n elements, where for security parameter k. Suppose the DDH assumption holds in with respect to a generator . That is, the distributions and are computationally indistinguishable.
1. [15 points] Show that $\{(\alpha^a,\alpha^b,\alpha^{ab})\}_{a,b\leftarrow \{1,\ldots,n-1\}}$ and $\{(\alpha^a,\alpha^b,\alpha^c)\}_{a,b,c\leftarrow \{1,\ldots,n-1\}}$ (i.e., the exponent 0 is avoided) are computationally indistinguishable.
2. [15 points] Show that if $n$ is a prime number then $\{(\beta,\gamma,\beta^r,\gamma^r)\}_{\beta,\gamma\leftarrow G\backslash\{\alpha^0\}; r\leftarrow\{1,\ldots,n-1\}}$ and $\{(\beta,\gamma,\beta^r,\gamma^s)\}_{\beta,\gamma\leftarrow G\backslash\{\alpha^0\}; r,s\leftarrow\{1,\ldots,n-1\}}$ are computationally indistinguishable. For this, given an adversary $A\,$ which has an advantage $\epsilon\,$ in distinguishing these distributions, show how to construct an adversary $A^*\,$ which can distinguish the distributions of the above example with advantage $\epsilon\,$ . Point out where you use the fact that $n$ is prime. (Remember that when $n$ is prime, the set $\{1,\ldots,n-1\}$ forms a group under multiplication modulo $n$ .)
[30 points] Elgamal encryption and the DDH assumption In class we saw that the Elgamal encryption scheme in a group $G$ is IND-CPA secure if the DDH assumption holds in the group. Prove the converse (that is, if Elgamal is secure then the DDH asssumption has to hold), by showing an adversary which uses a DDH distinguisher to gain advantage in the IND-CPA experiment.
[10 points] Square roots in $\mathbb{QR}^*_{P}$ , when $P$ Blum. Recall that squaring is a permutation in $\mathbb{QR}^*_{P}$ if $P\equiv3\mod 4\,$ . Show that for $x\in\mathbb{QR}^*_{P}$ , the inverse of this permutation (called the square root $\sqrt{x}$ ) is given by $x^{\frac{P+1}{4}}$ .