OWFs and Applications
The problems in this part will walk you through the key steps in the proof that weak OWFs (objects with a very weak form of cryptographic hardness) are sufficient to build PRFs, which we saw in the first week can be used to construct SKE. This is shown via a series of implications: wOWFs ⇒ OWFs ⇒ PRGs ⇒ PRFs. Every implication in this chain is a breakthrough work and a foundational staple of modern cryptography, so hopefully you will learn a lot by doing these problems.
Weak OWF⇒OWF The exercises in this section will walk you through the proof of an important theorem of Yao.
Definition 1 (Weak OWF). Let ε > 0 be non-negligible. We say that f : {0, 1} n → {0, 1} m is an ε−weak OWF if for all efficient adversaries A, the probability that A completes the function inversion task for f is at most 1 − ε. So intuitively, a weak OWF is a function that is sometimes hard to invert for every efficient adversary; whereas a OWF is almost always hard to invert for every efficient adversary. The next theorem is a famous result of Yao which shows how to use a weak OWF to build a OWF. Theorem (Yao’s Hardness Amplification). Suppose f : {0, 1} n → {0, 1} m is an ε−weak OWF for a non-negligible parameter ε > 0, and let k = 2n/ε. Then the k−wise product function F(x1, . . . , xk) = f(x1), . . . , f(xk) is a OWF from {0, 1} nk → {0, 1} mk . Intuition. The intuition behind the proof is that since an ε−fraction of the x ∈ {0, 1} n are such that y = f(x) is hard to invert, at least one of these hard y will appear in a random (y1, . . . , yk) with very high probability. Proof. Suppose A wins the OWF game of F with non-negligible probability 2δ > 0. We construct an efficient adversary B which plays the OWF game of f and uses A to win with probability greater than 1 − ε. This breaks the assumption that f is an ε−weak OWF. B plays against a challenger C as follows: 1. B receives y ∈ {0, 1} m from C. 2. B performs the following steps k 2n/δ times: · B chooses (x1, . . . , xk) ∼ {0, 1} nk and sets (y1, . . . , yk) = F(x1, . . . , xk) ∈ {0, 1} mk; then B chooses i ∼ [k] and overwrites yi with y; · B sends (y1, . . . , yk) to A; · if A returns (x 0 1 , . . . , x0 k ) ∈ {0, 1} nk such that F(x 0 1 , . . . , x0 k ) = (y1, . . . , yk) then B outputs x 0 i and halts; otherwise B continues. 3. B outputs FAIL and halts. First we set some shorthand. Let Dy be the distribution specified in the first bullet of Step 2. Specifically, Dy draws (x1, . . . , xk) ∼ {0, 1} nk, sets (y1, . . . , yk) = F(x1, . . . , xk) ∈ {0, 1} mk; then chooses i ∼ [k] and overwrites yi with y, outputting (y1, . . . , yk). Also, let us say that A(y1, . . . , yk) wins if A returns (x 0 1 , . . . , x0 k ) ∈ {0, 1} nk such that F(x 0 1 , . . . , x0 k ) = (y1, . . . , yk). Finally, we say that y ∈ {0, 1} m is bad, and write y ∈ BAD, if PrDy A(y1, . . . , yk) wins ≤ δ/k.
Problem 1. Complete the proof that Pr B inverts y > 1 − ε by doing the following. (a) Prove that if y /∈ BAD then Pr B inverts y = 1 − 2 −Ω(n) . Deduce that it suffices to show that Pry∼{0,1}m y /∈ BAD > 1 − ε/2. (b) Prove that Pr(y1,...,yk)∼{0,1}mk A(y1, . . . , yk) wins & ∃ i st yi ∈ BAD ≤ δ. Deduce that δ ≤ Pry∼{0,1}m y /∈ BADk . (c) Complete the proof by showing that if Pry∼{0,1}m y /∈ BAD ≤ 1 − ε/2, then δ ≤ 2 −n , a contradiction since δ is non-negligible.