Course:Fall 2006 Exercises 2

From CRYPTUTOR

Jump to: navigation, search

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

The solutions are due in class on Friday, September 29.

Exercises on One-Way Functions and Hardcore Predicates

  1. [10 pts] Existence of a one-way function \Rightarrow \mathrm{P}\not=\mathrm{NP}: For any function f:\{0,1\}^*\rightarrow \{0,1\}^*, define a language \mathsf{Preimageprefix}_f as \{(x,y)|\, \exists w such that f(y\circ w)=x\} (where \circ is the concatenation operator). That is, (x,y)\, is in the language if and only if y\, is a prefix of a preimage of x\,. Show that if \mathsf{Preimageprefix}_f can be decided using a polynomial time algorithm (polynomial time in its input length), then f\, is not a one-way function. Hence argue that if f\, is a one-way function, then \mathrm{P}\not=\mathrm{NP}.
  2. [10 pts] One-way, but every single bit of the preimage is predictable: For any function f:\{0,1\}^*\rightarrow \{0,1\}^*, define a function g_f\, as follows g_f(x,S)=(f(x|_S),S,x|_{\bar{S}}), where S is a subset of \{1,2,\ldots,|x|\} (represented as a bit vector of length | x | ). Here x|_S\, denotes a string obtained by choosing only those bits from x as specified by S and x|_{\bar S} 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\,.
  3. [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\,. Give a simple example of a function which is not one-to-one, has a hard-core bit and is not one-way.

Exercises on Indistinguishability, Pseudorandomness Generators and Hybrid Arguments

  1. [10 pts] Statistical and computational indistinguishability.
    1. Show that if two (ensembles of) distributions \mathcal{T} and \mathcal{V} over \{0,1\}^{\ell(k)} have negligible statistical difference between them (i.e., are statistically indistinguishable), then they are computationally indistinguishable.
    2. 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?
  2. [10 pts] PRG \Rightarrow OWF. Given a PRG G, construct a one-way function.
  3. [10 pts] Show that a PRG is also a Next Bit Unpredictable PRG.
  4. [10 pts] Uniform PRG and Uniform NBU PRG. Define a uniform PRG by modifying the definition of a PRG to consider only uniform adversaries. Similarly modify the definition of a Next Bit Unpredictable PRG to obtain the definition of a uniform NBU PRG. Show that a uniform NBU PRG is a uniform PRG. Point out how the proof differs from that of an NBU PRG being a PRG.
  5. [15 pts] Stream Ciphers, PRG and Stateful Encryption. A stream-cipher S is defined (for the purposes of this exercise) using a pair of deterministic, functions S_{\mathrm{out}}:\{0,1\}^k\rightarrow \{0,1\} and S_{\mathrm{update}}:\{0,1\}^k\rightarrow \{0,1\}^k. The security requirement is that, for any polynomial \ell, the function G_{S}:\{0,1\}^k\rightarrow \{0,1\}^{\ell(k)} defined as G_S(s)\mapsto S_{\mathrm{out}}(s)\,S_{\mathrm{out}}(S_{\mathrm{update}}(s))\,S_{\mathrm{out}}(S_{\mathrm{update}}^2(s))\,\ldots\,S_{\mathrm{out}}(S_{\mathrm{update}}^{\ell(k)-1}(s)) is a PRG.
    1. How would you construct a stream cipher from a one extra bit PRG?
    2. Can you reverse the process to construct a one extra bit PRG from a stream-cipher? Elaborate, with a proof or counter-example.
    3. Modify SIM-CPA (or IND-CPA) definition to allow a stateful encryption algorithm (i.e., the encryption algorithm remembers its state from one invocation to the next). Show how to use a stream cipher to construct a private-key encryption scheme, which is (modified) SIM-CPA secure, but with a stateful Alice (and a stateless Bob). Prove its security.
  6. [15 pts] An Application of the Hybrid Argument. Recall the definition of IND-CPA security for encryption. In the experiment involved, we allowed the adversary access to an encryption oracle, as well as allowed it to provide multiple pairs of plaintext challenges.
    1. Show that the adversary's access to encryption oracle can be removed from the definition, to get an equivalent security definition. (No hybrid argument here.)
    2. Use a hybrid argument to show that in the IND-CPA definition (allowing the adversary access to encryption oracle), the adversary can be restricted to sending only one challenge (i.e., pair of messages m0,m1) to the experiment, to get an equivalent security definition. (Use a hybrid argument. Consider the two distributions when b = 0 and when b = 1, as the end points of our hybrid sequence.)
    3. If we remove both the access to encryption oracle, and the multiple challenges simultaneously from the IND-CPA definition, does the security remain unchanged?
Retrieved from "http://crypto.cs.uiuc.edu/wiki/index.php/Course:Fall_2006_Exercises_2"