23 Analyzing the Success Probability

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

Assuming that b is not a hard core for g, there is a p.p.t. algorithm G and a polynomial p(n) such that G predicts b with advantage

(1)

for all n in an infinite set N. In section 22.2 of lecture 9, we constructed an algorithm A for inverting f. We now show that A has success probability at least at inverting f on length-n inputs, for all n N. This contradicts the assumption that f is strongly one-way and completes the proof of Lemma 3.

Assume for the rest of this discussion that n N. Let

Here R_n is a uniformly distributed random variable over length-n strings, distinct from the identically distributed random variables U_n and X_n, which we also mention from time to time. Thus, s(x) is the fine-grained success probability of G for each particular length-n string x. We know that the average of s(x) taken over all length-n strings x is the overall success probability of G, so

(2)

Define

(3)

Three different proofs of this claim are given in handout 3: One is algebraic, one is geometric, and one is based on Markov’s inequality. We do not repeat them here but refer the reader to the handout. We only mention that all three are based on the idea that in order for the average value of s(x) to exceed + ε(n), there must be a certain number of x for which s(x) ≥ + . That number turns out to be ε(n) ⋅ 2ⁿ.

Claim 2 ∀x S_n,∀i {1,…,n},

Proof: Let x S_n and i {1,…,n}. Let ζ^J be a random variable ranging over {0,1} such that

(4)

A key observation is that the ζ^J’s are pairwise independent. This follows from the fact that the r^J’s are pairwise independent. To see this, let J≠K. Without loss of generality, we can choose k K - J. By definition, r^K and r^J are both sums of subsets of the independent random variables {s¹,…,s^ℓ}. Since k K -J, the term s^k appears in the sum for r^K but not for r^J. Therefore, s^k is independent of r^J, which implies that r^K is independent of r^J.

Let m = 2^ℓ - 1. Since ℓ = ⌈log ₂(2n⋅p(n)² + 1)⌉, we have that 2^ℓ ≥ 2^{log ₂(2n⋅p(n)2+1)} = 2n⋅p(n)² + 1, so m ≥ 2n ⋅ p(n)². We also have

(5)

We use Chebyshev’s inequality to bound Pr[∑ _Jζ^J ≤ ⋅ m]. This is an upper bound on the probability that the majority value z_i that algorithm A computes for x_i is wrong. Recall Chebyshev’s inequality

(6)

Let X = ∑ _Jζ^J and δ = . All of the ζ^J are identically distributed, so we drop the superscript in the following.

by equation 4. Thus,

(7)

We also have

Since ζ is 0-1 valued, it follows that ζ² = ζ. Hence,

The bound of 1∕4 simply reflects the fact that the maximum value of the function x(1 - x), which is reached for x = 1∕2. Since the variables ζ^J are pairwise independent, they are also uncorrelated, so

(8)

Plugging the expression for δ into inequality 6 and doing some calculations using inequalities 7 and 8, we get

To finish the proof of the lemma, we observe that A successfully inverts f(x) if all of the following are true:

1. x S_n.
2. The guesses for the σⁱ are all correct, that is, σⁱ = b(x,s^I) for all i.
3. Each z_i that A produces is correct.

The first event is true with probability at least ε(n) ≥ by Claim 1. The second event is true with probability

by inequality 5. The third event is true with probability at least (1 -)ⁿ > for all n ≥ 2. Multiplying these together gives us a lower bound on the success probability of f, namely,

Thus, taking q(n) = 8n⋅p(n)³ + 4p(n), A has a success probability greater than for all sufficiently large n N, contradicting the assumption that f is strongly one-way. Thus, the assumption that b is not hard-core for f and that G exists must be false. This completes the proof of Lemma 3 of section 21.

24 Hard-Core Functions

We extend the notion of a hard-core predicate of a function to a hard-core function.

Definition: Let h : {0,1}^* → {0,1}^* be a polynomial-time computable length-regular function.¹ Let ℓ = |h(1ⁿ)|. h is a hard core of f if for all p.p.t. algorithms D′, all positive polynomials p(⋅), and all sufficiently large n,

where X_n and R_ℓ(n) are independent random variables, uniformly distributed over {0,1}ⁿ and {0,1}^ℓ(n), respectively.

Intuitively, h is a hard core for f if the value of h(x) is indistinguishable from a random string, even knowing the value of f(x). On the surface, this looks to be an even stronger condition than unpredictability. Obviously, if one could predict h(x) from f(x), then one could distinguish h(x) from random. Namely, if the given string equals the prediction, output 1, otherwise output 0. On the other hand, it’s not a priori obvious how being able to distinguish h(x) from random would be useful at prediction.

Theorem 1 Let f be strongly one-way. Let c > 0 and let ℓ(n) = min{n,⌈clog ₂n⌉}. Let x be a string of length n and s a string of length 2n. Define

Then h is a hard core of g₂.

We omit the non-trivial proof of this theorem and remark only that hard core functions with logarithmic lengths are known for RSA and other cryptographic collections, assuming the corresponding collections are one-way. Details are in the textbook.

25 Probability Ensembles

To begin our formal development of pseudorandom sequence generation, we define a probability ensemble, analogous to the previous definition of a collection of one-way functions.

Let I be a countable set. An ensemble indexed by I is a sequence of random variables X = {X_i}_iI indexed by I.

Typical index sets are the natural numbers ℕ or binary strings {0,1}^*. Typically, X = {X_n}_nℕ has X_n ranging over strings of length poly(n), and X = {X_w}_w{0,1}^* has X_w ranging over strings of length poly(|w|).

26 Polynomial Time Indistinguishability

We give two definitions of polynomial time indistinguishable ensembles, depending on the index set.

Variant 1: Ensembles X = {X_n}_nℕ and Y = {Y _n}_nℕ are indistinguishable in polynomial time if for all probabilistic polynomial time algorithms D, all positive polynomials p(⋅), and all sufficiently large n

Variant 2: Ensembles X = {X_w}_w{0,1}^* and Y = {Y _w}_w{0,1}^* are indistinguishable in polynomial time if for all probabilistic polynomial time algorithms D, all positive polynomials p(⋅), and all sufficiently large n

Easy consequences

Let D be a p.p.t. algorithm. Let d(α) be the probability that D(α) = 1. Let d_X(n) = E[d(X_n)], d_Y (n) = E[d(Y _n)], be the expected value of D’s output when given a string from X or from Y , respectively. Let

Then X and Y are indistinguishable by D iff δ is negligible in n.

Let wt(α) = # 1’s in α. If X, Y are polynomial-time indistinguishable, then

regarded as a function of n is negligible. (Why?)

Note: The same applies to any polynomial-time computable string statistic.