YALE UNIVERSITY

DEPARTMENT OF COMPUTER SCIENCE

CPSC 461b: Foundations of Cryptography | Notes 7 (rev. 1) | |

Professor M. J. Fischer | February 3, 2009 | |

Lecture Notes 7

We now complete the proof theorem 1 from lecture 6 by constructing a strongly one-way function g from a weakly one-way function f.

Let f be a weakly one-way function with associated polynomial p(⋅). Assume w.l.o.g. that f is
length-preserving. Let t(n) = n ⋅ p(n), and let T = {n ⋅ t(n)∣n ℕ}. Let g be the function on length
n⋅t(n) strings defined by g(x_{1},…,x_{t(n)}) = (f(x_{1}),…,f(x_{t(n)}), where |x_{1}|,…,|x_{t(n)}| = n. That is, given a
string x of length n ⋅ t(n), g splits it into t(n) length-n strings x_{1},…,x_{t(n)}, applies f(⋅) to each, and
concatenates the t(n) result strings so obtained.

Proof: Assume g is not strongly one-way on lengths in T . We proceed to derive a contradiction.

Since g is assumed not strongly one-way, there exists a p.p.t. algorithm B′ and a polynomial q(⋅) such that for infinitely many m T ,

| (1) |

Let M′ be the infinite set of integers for which inequality 1 holds, and let N′ = {n∣n^{2}p(n) M′}.

We describe a p.p.t. algorithm A′ for inverting f on input y. First consider the procedure I′ for inverting f.

Procedure I′(y): |

For i = 1 to t(n) do: |

1. Choose x_{1},…,x_{t(n)} {0,1}^{n} uniformly and independently. |

2. Compute (z_{1},…,z_{t(n)}) = B′(f(x_{1}),…,f(x_{i-1}),y,f(x_{i+1}),…,f(x_{t(n)})). |

3. If f(z_{i}) = y, then halt and output z_{i} and declare “success”. |

If f(z_{i})≠y for all i, then halt and declare “failure”. |

Now, algorithm A′(y) runs I′(y) repeatedly a total of a(n) = 2n^{2} ⋅p(n) ⋅q(n^{2}p(n)) times. If any of the runs of
I′(y) succeed, then A′ succeeds and gives the output of the first successful I′; otherwise, A′
fails.

For n N′, we will show that

contradicting the assumption that f is weakly one-way.

Let

be the set of good inputs of length n. Claim 1 shows that S_{n} is the set of inputs on which I′ succeeds
often enough so that A′ has an exponentially small failure probability.

Proof: Immediate since for x S_{n},

__

We now show in Claim 2 that almost all inputs x are in S_{n} for those lengths n that correspond to
values m = n^{2}p(n) M′ on which B′ has a success probability greater than 1∕q(m). (See inequality 1.)

Proof: Assume to the contrary that

| (2) |

and let m = n^{2}p(n). By inequality 1,

| (3) |

The random variable U_{m} consists of n ⋅ p(n) independent n-bit blocks U_{n}^{(1)},…,U_{n}^{(n⋅p(n))}.
Define

Clearly, s(n) = s_{1}(n) + s_{2}(n).

We derive a contradiction by showing that both s_{1}(n) and s_{2}(n) are bounded from above by
n^{2} ⋅ p(n)∕a(n).

Note that

| (4) |

This is because algorithm I′ succeeds on y = f(x) whenever B′ succeeds on g(U_{m}) and U_{n}^{(i)} = x.

Following the text, we have

Step (10) follows from inequality (4), and step (11) follows from the definition of S The following bound on s_{2}(n) holds for all sufficiently large n.

This contradicts (3), completing the proof of the claim. __

To finish the proof of the lemma, we observe that

follows immediately from claim 2, and

follows from claim 1 since the bound applies to every x S_{n}. Hence,