# Course:Fall 2007 Exercises 3

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

The solutions are due in class on Friday, October 12. Up to two problems (and any extra-credit problems) may be submitted on Wednesday, October 17. (Mention on your Friday submission which ones you are postponing.)

## Exercises on Block Ciphers and Public-Key Encryption

1. 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. [10 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.
2. Impossibility of information-theoretic public-key encryption.
1. [10 pts] Show that no public-key encryption scheme can be secure against computationally unbounded adversaries. More concretely, show that if $(\mathsf{KeyGen},\mathsf{Enc},\mathsf{Dec})$ is a public-key encryption scheme with perfect correctness (i.e., for all messages M and valid key-pairs (PK,SK), we have $\mathsf{Dec}_{SK}(\mathsf{Enc}_{PK}(M))=M$) then there is a function $\mathsf{Eve}$ such that for all messages M and valid public-keys PK, $\mathsf{Eve}_{PK}(\mathsf{Enc}_{PK}(M))=M$ (note that $\mathsf{Eve}$ uses only the public-key and not the secret-key.
2. [Extra Credit] (This problem uses information theoretic terminology.) Show an information theoretic statement that if Alice and Bob do not share private information, then whatever information Alice can convey to Bob using a public-key encryption scheme (which may or may not be perfectly correct), Eve gets the entire information. More precisely, show that for any probabilistic algorithms $\mathsf{KeyGen}$ and $\mathsf{Enc}$, I(PK,C;M) = I(PK,SK,C;M) where $(PK,SK)\gets\mathsf{KeyGen}$ and $C\gets\mathsf{Enc}_{PK}(M)$ and M comes from an arbitrary distribution.
3. [15 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. (Extra Credit. Is it in general true that a public-key encryption scheme yields a trapdoor PRG in the same way? Does it yield a trapdoor one-way function?)

## Exercises on Basic Algebraic/Number Theoretic Tools

1. [15 pts] Show that $\mathbb{Z}_N^*$ (for N = 2O(k), and elements represented as integers mod N) has all the computational properties required of a "computational group" (as defined in class).
2. [10 pts] Show that if the DDH assumption holds in a (computational) group collection, then the Discrete Logarithm assumption also holds in that collection. That is, given an adversary with a non-negligible advantage in the Discrete Logaithm experiment, give an adversary which gets a similar advantage in the DDH experiment.
3. Chinese Remainder Theorem.
1. [15 pts] In $\mathbb{Z}_{PQ}$ (where P,Q are relatively prime to each other), show how to convert a "CRT representation" into a number in the standard representation. That is, given $(a,b)\in\mathbb{Z}_P\times\mathbb{Z}_Q$ find $c\in\mathbb{Z}_{PQ}$ such that $a \equiv c \!\!\!\mod P$ and $b \equiv c \!\!\!\mod Q$. (Hint: First consider the cases when (a,b) = (1,0) and (a,b) = (0,1). You can either appeal to the extended Euclidean algorithm or use inversion of elements in the groups $\mathbb{Z}_P^*$ and $\mathbb{Z}_Q^*$.)
2. [10 pts] For any positive integer N (or you may consider N with at most two prime factors), and any positive integer e such that $\gcd(e,\varphi(N))=1$, show that there exists a positive integer d such that $(x^e)^d \equiv x \!\!\!\mod N$ for every $x\in\mathbb{Z}_N$. (Here exponentiation is as integers.) (Hint: To show that the d you give works, work with the CRT representation of x.)
4. [Extra Credit] Square-root modulo PQ and factoring. Suppose A is an algorithm for finding square roots in $\mathbb{Z}_N^*$, where N = PQ, for P,Q primes. That is given $z\in\mathbb{QR}_N^*$, A will return $x\in\mathbb{Z}_N^*$ such that x2 = z in $\mathbb{Z}_N^*$ (say, with probability 1). Consider the following algorithm A * for factoring N: Pick $r\gets\mathbb{Z}_N^*$ and let $z\gets A(r^2)$ (so that z2 = r2). If gcd(N,rz) > 1 or gcd(N,r + z) > 1 (computation as integers), then output it as a factor of N (else fail and halt). Show that with probability half A * outputs a factor of N. (Hint: z2 has 4 distinct square-roots, namely $\pm r_1$ and $\pm r_2$ (for some r1,r2), all of which are chosen equally likely by A * as r.)