YALE UNIVERSITY
DEPARTMENT OF COMPUTER SCIENCE

	CPSC 461b: Foundations of Cryptography	Notes 9 (rev. 2)
Professor M. J. Fischer		February 10, 2009

Lecture Notes 9

22 Proving a Predicate is Hard-Core

We continue the proof of Lemma 3 of section 21. Recall that f is a strongly one-way and length preserving function, and that

df g(x,r) = (f (x ),r) df b(x,r) = x ⋅r mod 2.

We showed in Lemma 2 that g is strongly one-way. We want to show that b is a hard core for g.

Assume to the contrary that b is not a hard core for g. Then there exists a p.p.t. algorithm G that predicts b with non-negligible advantage ε_G(n). Thus, there is a polynomial p(⋅) such that

Pr[G(f (U ),X ) = b(U ,X )] ≥ 1-+--1- n n n n 2 p(n)

(1)

for all n in an infinite set N.

To complete the proof of Lemma 3, we will do two things:

We will construct an algorithm A that on input y attempts to invert f.
We will show that, for some polynomial q(⋅), A has success probability greater than at inverting f on length n inputs for all sufficiently large n in the infinite set N. This contradicts the assumption that f is strongly one-way.

We construct A now and defer the analysis of its success probability to the next lecture.

22.1 Using G to invert f

How can G help us to invert f? A priori it doesn’t seem to be much help to have a predictor for only a single predicate when our algorithm A is supposed to correctly output a length-n string in f^-1(y). It’s not at all obvious how to use G, and several tricks are involved.

Using b to extract bits of x: Let eⁱ be the unit vector with a 1-bit in position i and 0’s elsewhere. As before, we treat strings in {0,1}^* as bit-vectors, so x_i is the i^th bit of x. It follows from the definition of Boolean dot product that b(x,eⁱ) = x ⋅ eⁱ mod 2 = x_i.

Fact

b(x,r) ⊕ b(x,r ⊕ ei) = xi.

(2)

This follows because

( n ) ( n ) b(x,r) ⊕ b(x, s) = ( ⊕ x ⋅r) ⊕ ( ⊕ x ⋅s) j j j j j=1 j=1 ⊕n = (xj ⋅(rj ⊕ sj)) j=1 = b(x, r ⊕ s) (3)

Taking s = r ⊕ eⁱ, equation 3 gives

i i i b(x,r)⊕ b(x,r ⊕ e ) = b(x,r ⊕ (r ⊕ e)) = b(x,e) = xi

(4)

as desired.

First idea for A: For each i = 1,…,n, use G to guess b(x,r) and b(x,r ⊕eⁱ) for random r, then use equation 4 to guess x_i, i.e., guess x_i = G(y,r) ⊕G(y,r ⊕eⁱ). Repeat this procedure to obtain polynomially many guesses of x_i and choose the majority value. Return x = x₁…x_n as the guess for f^-1(y).

If G is correct about b on both calls, then x_i is correct. As long the probability that both calls on G are correct is greater than 1
2 + -1-
poly , repetition will amplify this probability to be sufficiently close to 1 so that the probability of all n bits of x being correct is also close to 1. Unfortunately, this is only the case when G’s success probability is 3
4 + 1
poly , that is, its advantage is a little bit greater than . All we know about our G is that it satisfies inequality 1, so its advantage is only --1-
p(n) .

Second idea for A: Same as first idea, except instead of using G to guess b(x,r), we just use a random bit (r). Thus, we guess that x_i = (r) ⊕ G(y,r ⊕ eⁱ). This of course doesn’t work since the probability of being correct is exactly 1
2 and we get no advantage. But if we somehow had an oracle that would give us the correct value for ˆ
b (r) = b(x,r), then this idea would indeed work since then the advantage at guessing x_i would be the same as G’s advantage at guessing b.

Third idea for A: We generate a small (O(log n)-sized) set of random strings R₀ and corresponding guesses for (r) for each r R₀. From R₀, we deterministically generate a polynomial set of strings R and corresponding values for (r), r R. By the way the construction will work, if (r) is correct for all r R₀, then (r) is correct for all r R. Since the number of strings in R₀ for which we require correct guesses is only O(log n), it follows that the probability of all O(log n) guesses being correct is at least po1ly since 2^{O(log n)} = poly(n).

The strings in R are uniformly distributed over {0,1}ⁿ, but they are only pairwise independent. However, this turns out to be sufficient for the construction to work.

How to generate R₀ and R: Let ℓ = ⌈log ₂(2n ⋅ p(n)² + 1)⌉.

Select s¹,…,s^ℓ {0,1}ⁿ uniformly and independently. Select σ¹,…,σ^ℓ {0,1} uniformly and independently. Let R₀ = {s¹,…s^ℓ} and (sⁱ) = σⁱ, i = 1,…,ℓ.
Let be the family of non-empty subsets of {1,2,…,ℓ}. For all sets J , compute $⊕ ⊕ rJ = sj and ρJ = σj. j∈J j∈J$
Let R = {r^J∣J }, and (r^J) = ρ^J for all J .

Note that r^{i} = sⁱ and ρ^{i} = σⁱ, so indeed R ⊇ R₀.

Fact If b(x,s^j) = σ^j for all j {1,…,ℓ}, then b(x,r^J) = ρ^J for all J .

This follows because

⊕ ⊕ ⊕ b(x,rJ) = b(x, sj) = b(x,sj) = σj = ρJ . j∈J j∈J j∈J

The first equality is from the definition of r^J, the second comes from repeated use of equation3, the third uses the assumption that σ^j is correct for all j

{1,…,ℓ}, and the final equality is from the definition of ρ^J.

22.2 The complete algorithm for A

Here is the complete algorithm for A. On input y, let n = |y| and ℓ = ⌈log ₂(2n ⋅ p(n)² + 1)⌉.

Uniformly and independently, select s¹,…,s^ℓ {0,1}ⁿ and σ¹,…,σ^ℓ {0,1}.
For all non-empty J ⊆{1,2,…,ℓ}, compute $J ⊕ j J ⊕ j r = s and ρ = σ . j∈J j∈J$
For all i {1,…,n}, for all non-empty J ⊆{1,…,ℓ}, compute $zJi = ρJ ⊕ G(y,rJ ⊕ ei).$
For all i {1,…,n}, let z_i = majority_J{z_i^J}.
Output z = z₁…z_n.