YALE UNIVERSITY
DEPARTMENT OF COMPUTER SCIENCE
 CPSC 461b: Foundations of Cryptography  Notes 13 (rev. 1) 
Professor M. J. Fischer   February 24, 2009 




32 Review of Lecture 12
Lecture 12 covered several technical proofs fairly quickly. In this lecture, we reviewed the three theorems
from last time and focused on the key ideas that made the proofs work. (The complete proofs are contained
in the written notes for Lecture 12.)

Building G from G_{1}:
 The big idea that makes the hybrid proof work is that the distinguisher D′ is
given as argument either α = G_{1}(U_{n}) or α = U_{n+1}. In either case, it splits α into two parts
τ ⋅α′ and constructs the string w = τ ⋅G(α′). If α = G_{1}(U_{n}), then w = τ ⋅G(α′) = G(U_{n}).
If α = U_{n}, then w = U_{1} ⋅ G(U_{n}). Hence, the difference is simply whether w starts directly
with the bits from G(U_{n}) or whether it starts with a random bit τ followed by G(U_{n}). This
fits in with the construction of the hybrids, so when w is prefixed with a random β of lengthk
and truncated to total length p(n), the resulting hybrid is either H_{n}^{k} or H_{n}^{k+1}.

Pseudorandom ⇐ Unpredictable:
 Here, the hybrids are strings with k bits from the
pseudorandom generator followed by n  k random bits. Assume D is a distinguisher for
the pseudorandom strings. The nextbit predictor A that we construct generates a hybrid for a
randomlychosen k and then calls the distinguisher D on it. A outputs the first of the n  k
random bits if the distinguisher answers 1, and it outputs the complement otherwise. This
works since D was assumed to be more likely to output 1 on pseudorandom strings than on
truly random ones.

Pseudorandom implies strongly oneway
 Given a pseudorandom function G(s) with expansion
factor 2n, the proof constructs the function f(x,y) = G(x) and proceeds to derive a
contradiction to the assumption that f is not strongly oneway. While f is attractive because
it is lengthpreserving, it seems that the proof goes through just fine for G itself. Assume
G were not strongly oneway, and let A be an algorithm that inverts it with nonnegligible
success probability. Then here’s how to distinguish G(s) from U_{2n}. On input α, use A to find
s′ such that G(s′) = α. If such an s′ is found, output 1; else output 0. If the input is α = G(s),
the distinguisher will output 1 with probability the same as A’s success probability, which is
at least for some polynomial p(⋅). If the input is α = U_{2n}, then the distinguisher will
output 0 whenever U_{2n} is not in the range of G(s) (as s ranges over lengthn strings). The
size of the range is 2^{n} but the number of choices for α is 2^{2n}, so the probability of giving
output 1 in this case is at most 2^{n}∕2^{2n} = 1∕2^{n}. Hence, the difference in probabilities is at
least  > , contradicting the assumption that G is pseudorandom.
33 Pseudorandom Generator from Strongly OneWay Permutation
The construction of a pseudorandom generator from an arbitrary strongly oneway function is complicated
and not included in the textbook. However, if strongly oneway permutations exist, then it is
straightforward to construct a pseudorandom generator.
Theorem 1 Let f be a lengthpreserving 11 strongly oneway function and b a hard core for f.
Then
is a pseudorandom generator.
Proof: Assume G is not pseudorandom. Then there exists a bit predictor A with significant
advantage. Let α = G(s), where s = U_{n}. Because f is 11, f(U_{n}) is uniformly distributed on
lengthn strings, so A can’t predict any of the first n bits of α with any advantage. Since A does
have an advantage overall, then it must have an advantage at predicting bit n+1. But this means that
A is able to get an advantage at predicting b(s) after having read f(s), contradicting the assumption
that b(s) is a hard core for f. __
Theorem 1 gives an easy and efficient method for constructing a polynomialexpansion pseudorandom
number generator given a strongly oneway permutation f with a hard core predicate b. Namely, on initial
seed s, do the following:
 7.  Output σ_{1}…σ_{p(n)}. 
34 Pseudorandom Functions
An ℓbit function ensemble is a sequence F = {F_{n}}_{nℕ} of random variables such that F_{n} assumes values
in the set of functions mapping ℓ(n)bitlong strings to ℓ(n)bitlong strings. The uniform ℓbit function
ensemble, H = {H_{n}}_{nℕ}, has H_{n} uniformly distributed over the set of all functions mapping
{0,1}^{ℓ(n)} →{0,1}^{ℓ(n)}.
Definition: An ℓbit function ensemble F is pseudorandom if, for every probabilistic
polynomialtime oracle machine M, every positive polynomial p(⋅), and all sufficiently large n,
Definition: An ℓbit function ensemble F is efficiently computable iff there exist polynomialtime
algorithms I, V such that
 ϕ(I(1^{n})) and F_{n} are identically distributed, where ϕ maps strings to functions. (Think of the
strings as somehow describing functions, and ϕ(i) is the function that the string i describes.)
 V (i,x) = f_{i}(x) for every i in the range of I(1^{n}) and x {0,1}^{ℓ(n)}, where f_{i} = ϕ(i) is the
function described by i.
In the next lecture, we will show how to construct an efficiently computable ℓbit pseudorandom
function ensemble, starting from a pseudorandom generator G with expansion factor 2n.