Course:Fall 2007 Exercises 2

From CRYPTUTOR

Revision as of 11:42, 18 September 2007; view current revision
←Older revision | Newer revision→

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

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

[edit]

Exercises on One-Way Functions and Hardcore Predicates

Existence of a one-way function $\Rightarrow$ $\mathrm{P}\not=\mathrm{NP}$ : For any function , define a language as such that (where is the concatenation operator). That is, is in the language if and only if is a prefix of a preimage of .
1. [8 pts] Show that if $\mathsf{Preimageprefix}_f$ can be decided using a polynomial time algorithm (polynomial time in its input length), then show that $f\,$ is not a one-way function (i.e., one can efficiently invert $f\,$ ).
2. [2 pts] On the other hand note that if $f\,$ is polynomial time computable, then $\mathsf{Preimageprefix}_f \in \mathrm{NP}$ . Hence conclude that if $f\,$ is a one-way function, then $\mathrm{P}\not=\mathrm{NP}$ .
[10 pts] One-way, but every single bit of the preimage is predictable: For any function , define a function as follows , where S is a subset of (represented as a bit vector of length | x | ). Here denotes a string obtained by choosing only those bits from x as specified by S and contains the remaining bits.
1. Show that if $f$ is a one-way function, then so is $g_f\,$ .
2. Show that no single bit of the input is a hard-core bit for $g_f\,$ .
[10 pts] If it has a hard-core bit, then it is one-way: Show that if a one-to-one, polynomial time computable function $f\,$ has a hard-core bit, then the function is one-way. Explain where in your argument did you use the one-to-one property and the polynomial time computability of $f\,$ .

[edit]

Exercises on Indistinguishability, Pseudorandomness Generators and Hybrid Arguments

Statistical and computational indistinguishability.
1. [3 pts] Show that if two (ensembles of) distributions $\mathcal{T}$ and $\mathcal{V}$ over $\{0,1\}^{\ell(k)}$ have negligible statistical distance between them (i.e., are statistically indistinguishable), then they are computationally indistinguishable.
2. [7 pts] Suppose $G:\{0,1\}^k\rightarrow\{0,1\}^{\ell(k)}$ is a PRG. Suppose $G$ is one-to-one. What is the statistical distance between the uniform distribution $\mathcal{U}_{\ell(k)}$ and the distribution $\{G(s)\}_{s\leftarrow\mathcal{U}_k}$ ? What if $G$ is not one-to-one?
[15 pts] PRG $\Rightarrow$ OWF. Given a PRG $G$ , construct a one-way function (with proof).
Stream Ciphers and PRG.
1. [7 pts] Show that a stream cipher can be constructed from a PRG (with a fixed stretch $\ell(k)-k > 0$ ).
2. [1 pts] Show that a PRG of any polynomial stretch can be constructed from a stream cipher.
3. [2 pts] If you take a PRG and convert it to a stream cipher (as in part 1) and then convert that back to a PRG (as in part 2) do you get back the original PRG?
Equivalence of IND-PRG and NBU-PRG.
1. [5 pts] Show that a PRG (defined using the IND-PRG definition) is also a Next Bit Unpredictable PRG.
2. [10 pts] Complete the argument (from Lecture 4) that a Next Bit Unpredictable PRG is a PRG according to the IND-PRG definition.
3. [Extra-credit] In the above did you use a uniform adversary or a non-uniform adversary? Modify the arguments so that they work for the other case too.
[20 pts] An Application of the Hybrid Argument. In the definition of IND-CPA security for encryption, the adversary is allowed to send multiple pairs of challenge messages. Consider modifying this definition so that the adversary can send only one pair, but in addition gets oracle access to the encryption (i.e., it can send a message $m\,$ and get back an encryption using the secret key). Show that this yields an equivalent definition. (Hint: First argue that adding the encryption oracle does not change the definition. Then use a hybrid argument to argue that negligible advantage with a single challenge implies negligible advantage with multiple challenges. Consider the two distributions when $b = 0$ and when $b = 1$ (in the multiple-challenges experiment), as the end points of our hybrid sequence.)