Problem 1 One-way functions and collections of one-way functions

[Textbook, Chapter 2, Exercise 18.]

Solution

1. The sampling algorithm (I,D) on input 1ⁿ can be seen as a function mapping q(n) bits (the internal coin tosses) to a pair (i,x), where q(n) is polynomial of n (number of internal coin tosses), i ∩{0,1}ⁿ and x D_i. Denoting this function as S_n, it is easy to see that

   where I_n is the output distribution of algorithm I on input 1ⁿ, and X_n is the output of algorithm D on input I_n.

   A new function g can be defined as such: for each z {0,1}^q(n), represent that S_n(z) = (i,x), thus g(z) = (i,f_i(x)). It also follows that g(U_q(n)) = (I_n,f_In(X_n)).

   We will show that the above g is a one-way function.

   Function g is polynomial-time computable since S_n can be computed by the polynomial-time algorithms I and D and f_i can be computed by the polynomial-time algorithm F .

   Suppose that g is polynomial-time invertable, namely, there exists a polynomial-time algorithms A such that for some polynomial p(n),

   

   Define a new algorithm B as such: for each input y = (i,f_i(x)) where i ∩{0,1}ⁿ and x D_i, represent that S_n(A(1^q(n),y)) = (j,z), where j {0,1}ⁿ and such that B(y) = z. We show that B inverts the collection (I,D,F).

   Since g(U_q(n)) = (I_n,f_In(X_n)), the event that A(1^q(n),g(U_q(n))) g^-1(g(U_q(n))) is equivalent to the event that A(1^q(n),(I_n,f_In(X_n))) g^-1(I_n,f_In(X_n)), which according to the definition of B, holds only if B(I_n,f_In(X_n)) f^-1(f_In(X_n)). Therefore,

   
   which is contra to the assumption that (I,D,F) is a one-way collection.
2. Given a one-way function f, a one-way collection (I,D,F) can be defined as such: I(1ⁿ) always outputs 0ⁿ, D(0ⁿ) samples uniformly over the domain of f, and F(0ⁿ,x) = f(x).

Problem 2 Hard core of one-way function

[Textbook, Chapter 2, Exercise 24, as modified below.]

Note that the “Guideline” is poorly printed and easy to misinterpret. The second subscript “x ” on the right side of the definition of g is , not I, but it takes sharp eyes to spot the difference in the printed version of the book. Here, is intended to denote the set difference {1,2,…,|x|}- I.

Also, we are used to dealing with functions on strings, yet the guideline defines g to take a set argument. There are many ways of representing finite sets by strings. For this problem, represent the set I ⊆{1,2,…,|x|} by the length-|x| bit-vector u, where u_i = 1 iff i I. It follows that is represented by ¬u, the bitwise complement of u.

Finally, we define x[u] = x_i1…x_ik, where i_j is the position of the j^th 1-bit in u, and k is the number of 1-bits in u. Thus, if u represents the set S, then x[u] denotes the string x_S defined in the guideline.

Using these conventions, the intended function g is defined by

You may ignore the part of the guideline that talks about more “dramatic” predictability.

Solution

We take the function g(x,u) = (f(x[u]),x[¬u],u) defined in the problem guideline. For each input (x,u), let b_i(x,u) denote the ith bit of the input.

Let A_i be such an algorithm: for each input in the form of (f(x[u]),x[¬u],u) if i > |u| (size of the set u), return the (i -|u|)th bit of the binary representation of u; if i ≤|u| and iu, return x_i which is contained in x[¬u]; and if otherwise, flip a fair coin and return the outcome.

It is easy to see that it always holds that A_i(g(x,u)) = b_i(x,u) for i > |u|, i.e. Pr[A_i(g(U_n)) = b_i(x,u)] = 1 for i > |u|.

For i ≤|u|, A_i(g(x,u)) = b_i(x,u) when iu, or if i u and A_i makes a correct guess. According to the total probability, for i ≤|u|,

Problem 3 Amplification

Amplification is the technique for reducing errors in probabilistic algorithms by repeating the computation many times. We have used amplification both for reducing the error probability in algorithms attempting to invert one-way functions and also for increasing the advantage of algorithms attempting to guess hard core predicates. However, the way it is used differs markedly in the two cases.

For inverting functions, we assume an algorithm A(y) succeeds with probability at least ϵ(n) at returning a value x f^-1(y). To amplify, we repeat A(y) for r(n) times and succeed if any of the runs succeed. This depends on our ability to feasibly test whether the value returned by A(y) in a given run is correct or not. Hence, the amplified success probability is at least

For guessing the value of a hard core predicate, we assume an algorithm D(y) with advantage ϵ(n) at predicting b(x). To amplify, we repeat D(y) for r(n) times. Because we do knot know which runs of D(y) return correct answers, we select our final answer to be the majority of all returned answers. The advantage of the resulting algorithm D′ is not easy to compute directly, so we use the Chernoff bound or other statistical techniques to get a lower bound on it.

Questions: Suppose ϵ(n) = = .

1. Show that for all positive polynomials p(⋅) and all sufficiently large n that ϵ(n) < .
2. Suppose ϵ(n) is the success probability for algorithm A. Find as small a function r(n) as you can such that repeating A for r(n) times results in a success probability greater than 1∕2 for all sufficiently large n.
3. Suppose ϵ(n) is the advantage of algorithm D. Find as small a function r(n) as you can such that repeating D for r(n) times and taking the majority gives an advantage greater than 1∕4 for all sufficiently large n.

Solution

1. Let LHS(n) = -log ₂ϵ(n) = (log ₂n)², and RHS(n) = -log ₂p(n). Since p(⋅) is a polynomial, RHS(n) ≥ C log ₂n for some constant C which is independent of n.

   For all n > 2^C, it holds that log ₂n > C, thus RHS(n) = (log ₂n)² < C log ₂n ≤ RHS(n). Since -log ₂(⋅) is monotonically decreasing, it must holds all the above n that ϵ(n) = 2^-LHS(n) < 2^-RHS(n) = .

2. Since the runnings of algorithm are independent, the probability that all r = r(n) trails fail is (1 - ϵ)^r. We want this probability to be less than 1∕2.
   
   To have (1 -ϵ)^r < 1∕2, it requires that exp < 1∕2. Solving this inequality we have that r(n) > n^{log ₂n} ⋅ ln2.
3. Let X_i be the random variable which indicates ith trial of D succeeds, it holds that X_i = 1 with probability + ϵ and X_i = 0 with probability - ϵ. The probability that the majority fails is
   
   The advantage is 1∕4, thus the probability that bad thing happens is less than 1∕2 - 1∕4 = 1∕4 i.e. q < 1∕4. To make q < , it requires that r(n) > ( - 2)ln8 = (n^{2 log ₂n} - 2)ln8.