YALE UNIVERSITY

DEPARTMENT OF COMPUTER SCIENCE

CPSC 461b: Foundations of Cryptography | Handout #6 | |

Yitong Yin | March 1, 2009 | |

Solutions to Problem Set 2

Originally due Thursday, February 26, 2009.

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

[Textbook, Chapter 2, Exercise 18.]

- The sampling algorithm (I,D) on input 1
^{n}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}^{n}and x D_{i}. Denoting this function as S_{n}, it is easy to see thatwhere I

_{n}is the output distribution of algorithm I on input 1^{n}, 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}^{n}and x D_{i}, represent that S_{n}(A(1^{q(n)},y)) = (j,z), where j {0,1}^{n}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, - Given a one-way function f, a one-way collection (I,D,F) can be defined as such: I(1
^{n}) always outputs 0^{n}, D(0^{n}) samples uniformly over the domain of f, and F(0^{n},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.

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|,

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.

- Show that for all positive polynomials p(⋅) and all sufficiently large n that ϵ(n) < .
- 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.
- 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.

- Let LHS(n) = -log
_{2}ϵ(n) = (log_{2}n)^{2}, and RHS(n) = -log_{2}p(n). Since p(⋅) is a polynomial, RHS(n) ≥ C log_{2}n for some constant C which is independent of n.For all n > 2

^{C}, it holds that log_{2}n > C, thus RHS(n) = (log_{2}n)^{2}< C log_{2}n ≤ RHS(n). Since -log_{2}(⋅) is monotonically decreasing, it must holds all the above n that ϵ(n) = 2^{-LHS(n)}< 2^{-RHS(n)}= . - 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.^{r}< 1∕2, it requires that exp < 1∕2. Solving this inequality we have that r(n) > n^{log 2n}⋅ ln2. - 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^{2 log 2n}- 2)ln8.