47.06.01 · theoretical-cs / 06-cryptographic-foundations

One-Way Functions and Pseudorandom Generators

shipped3 tiersLean: none

Anchor (Master): Arora and Barak 2009 Computational Complexity: A Modern Approach (Cambridge) Ch. 9; Håstad, Impagliazzo, Levin and Luby 1999 A Pseudorandom Generator from any One-Way Function (SIAM J. Comput.) (HILL construction: OWF implies PRG)

Intuition Beginner

Imagine a padlock. Anyone can snap it shut in a second. But opening it without the key takes much longer. A one-way function is the mathematical equivalent: a function that is easy to compute but hard to reverse.

Multiply two large prime numbers: $61 \times 53 = 3233$ . This is fast. But given 3233, finding that $61 \times 53$ is the factorisation takes much longer (for numbers with hundreds of digits, no known algorithm can do it efficiently). This asymmetry is the engine of modern cryptography.

A pseudorandom generator (PRG) stretches a small amount of true randomness into a large amount of randomness that looks random to any efficient algorithm. It takes a short seed of truly random bits and outputs a longer string that no polynomial-time test can distinguish from truly random bits. The existence of PRGs is equivalent to the existence of one-way functions: if you have a one-way function, you can build a PRG, and vice versa.

The deep insight is that computational hardness and pseudorandomness are the same thing in disguise. A function that is hard to invert gives you a source of bits that no efficient algorithm can predict. This is the foundation upon which all of cryptography is built: encryption, digital signatures, zero-knowledge proofs—all reduce to the existence of one-way functions.

Visual Beginner

One-way function:

  x (easy to compute) -> f(x)
  x = "password123"      f(x) = 0x7a2b9c...
  
  f(x) (hard to invert) -/-> x
  Given 0x7a2b9c..., finding "password123" takes exponential time

Pseudorandom generator:

  Seed (truly random, short)    Output (pseudorandom, long)
  128 bits  ----[PRG]---->  10000 bits
  
  No efficient algorithm can tell the output from 10000 truly random bits
  (unless it can invert the one-way function underlying the PRG)

Concept	Input	Output	Hardness
One-way function	$x$	$f (x)$	Inverting $f$ is hard
Hard-core predicate	$(x, r)$	$⟨ x, r ⟩$	Predicting bit is hard given $f (x), r$
PRG	Short seed $s$	Long pseudorandom string	Distinguishing from random is hard

Worked example Beginner

We illustrate a simple one-way function candidate. Define $f : {0, 1}^{n} \times {0, 1}^{n} \to {0, 1}^{2 n}$ by $f (x, y) = (g^{x} mod p, g^{y} mod p)$ where $p$ is a large prime and $g$ is a generator of $Z_{p}^{*}$ .

Computing $f$ is fast: modular exponentiation takes $O (n^{3})$ time using repeated squaring.

Inverting $f$ requires solving the discrete logarithm problem: given $g^{x} mod p$ , find $x$ . For a 2048-bit prime $p$ , the best known algorithms take roughly $2^{112}$ operations. This is infeasible.

Now, from $f$ we extract a pseudorandom bit using the Goldreich-Levin hard-core predicate: $h (x, r) = x \cdot r mod 2$ (the inner product of $x$ and $r$ modulo 2, for a random $r$ ). Given $f (x) = g^{x} mod p$ and a random $r$ , predicting $x \cdot r mod 2$ is as hard as inverting $f$ .

To build a PRG: start with seed $(x_{0}, r)$ . At each step $i$ , compute $x_{i + 1} = f (x_{i})$ and output bit $b_{i} = h (x_{i}, r)$ . After $k$ steps, we have stretched $2 n$ bits to $2 n + k$ bits. Each output bit is pseudorandom because predicting it requires inverting $f$ .

Check your understanding Beginner

Formal definition Intermediate+

Definition (one-way function). A function $f : {0, 1}^{*} \to {0, 1}^{*}$ is one-way if:

(Easy to compute) There exists a polynomial-time algorithm computing $f$ .
(Hard to invert) For every probabilistic polynomial-time (PPT) algorithm $A$ , every polynomial $p$ , and sufficiently large $n$ :

x \in {0, 1}^{n} Pr [A (1^{n}, f (x)) \in f^{- 1} (f (x))] < \frac{1}{p ( n )} .

Definition (negligible function). A function $μ : N \to R^{+}$ is negligible if for every polynomial $p$ and sufficiently large $n$ , $μ (n) < 1/ p (n)$ .

Definition (hard-core predicate). A polynomial-time computable function $h : {0, 1}^{*} \to {0, 1}$ is a hard-core predicate for $f$ if for every PPT algorithm $A$ :

x \in {0, 1}^{n} Pr [A (f (x)) = h (x)] \leq \frac{1}{2} + negl (n) .

Definition (pseudorandom generator). A deterministic polynomial-time function $G : {0, 1}^{s (n)} \to {0, 1}^{n}$ with $s (n) < n$ is a pseudorandom generator if for every PPT distinguisher $D$ :

∣ z \in {0, 1}^{s (n)} Pr [D (G (z)) = 1] - y \in {0, 1}^{n} Pr [D (y) = 1] ∣ \leq negl (n) .

The quantity $n - s (n)$ is called the stretch of $G$ .

Counterexamples to common slips

"One-way functions exist." This is not proven. It is a computational assumption. If P = NP, one-way functions do not exist (since inverting $f$ is an NP search problem). The existence of OWFs implies P $\neq =$ NP.
"A PRG produces truly random bits." The output is deterministic given the seed. It is pseudorandom: indistinguishable from truly random bits by any polynomial-time algorithm. An algorithm with unbounded time can distinguish it (by trying all seeds).
"Hard-core predicates are hard to compute." They are easy to compute given $x$ . They are hard to compute given only $f (x)$ , without knowing $x$ .

Key theorem with proof Intermediate+

Theorem (Goldreich-Levin). If $f$ is a one-way function, then $h (x, r) = ⟨ x, r ⟩ = \sum_{i} x_{i} r_{i} mod 2$ is a hard-core predicate for $g (x, r) = (f (x), r)$ .

Proof sketch. Suppose for contradiction that there exists a PPT algorithm $A$ such that $Pr [A (f (x), r) = ⟨ x, r ⟩] \geq 1/2 + ε$ for non-negligible $ε$ . We use $A$ to invert $f$ .

Given $y = f (x)$ , we want to recover $x$ . The idea is to learn $x$ one bit at a time using the Fourier coefficients of the predictor $A$ . Define $p (r) = Pr [A (y, r) = ⟨ x, r ⟩]$ . If we know $x$ , we can predict $⟨ x, r ⟩$ perfectly; $p (r) = 1$ .

The algorithm uses a list-decoding approach. For each candidate $z$ , define $p_{z} = Pr_{r} [A (y, r) = ⟨ z, r ⟩]$ . The correlation $\hat{A} (z) = E_{r} [(- 1)^{A (y, r) + ⟨ z, r ⟩}]$ is the Fourier coefficient of the predictor at $z$ . By Parseval's theorem, $\sum_{z} \hat{A} (z)^{2} = 1$ , so at most $1/ ε^{2}$ values of $z$ have $∣ \hat{A} (z) ∣ \geq ε$ .

The Goldreich-Levin algorithm recovers all $z$ with $∣ \hat{A} (z) ∣ \geq ε$ in time $O (n^{2} / ε^{4})$ by: (1) estimating $\hat{A} (z)$ for each $z$ by sampling random $r$ , and (2) using the self-correction trick: for any $r$ , $⟨ x, r ⟩ = ⟨ x, r \oplus e_{i} ⟩ \oplus x_{i}$ where $e_{i}$ is the $i$ -th unit vector, so querying $A$ at $r$ and $r \oplus e_{i}$ recovers $x_{i}$ .

This gives a PPT inverter for $f$ , contradicting one-wayness. $□$

Bridge. The Goldreich-Levin theorem is the foundational reason one-way functions yield pseudorandomness: by extracting a hard-to-predict bit from the input to a one-way function, we obtain a single pseudorandom bit, and iterating this extraction builds a full PRG. This builds toward the HILL theorem that any OWF implies a PRG, which appears again in 47.06.02 where specific number-theoretic OWFs (factoring, discrete log) give concrete PRG instantiations. The central insight is that computational hardness is convertible into pseudorandomness via a generic transformation, and this is exactly the pattern that generalises from theoretical cryptography to the derandomisation results of 47.05.05 where Nisan's PRG uses a different hardness source (space lower bounds) for a different purpose. Putting these together with the zero-knowledge proofs of 47.06.03 shows that OWFs are the universal primitive from which all cryptographic objects can be constructed.

Exercises Intermediate+

Exercise 3 (medium, symbolic).

Prove that a PRG with stretch 1 (mapping $n$ bits to $n + 1$ bits) can be iterated to produce a PRG with polynomial stretch (mapping $n$ bits to $n^{c}$ bits for any constant $c$ ).

Hint

Apply the PRG repeatedly, using the first $n$ bits of each output as the seed for the next invocation and collecting the extra bit each time.

Answer

Let $G : {0, 1}^{n} \to {0, 1}^{n + 1}$ be the PRG with stretch 1. Write $G (s) = G_{0} (s) ∥ G_{1} (s)$ where $G_{0} (s) \in {0, 1}^{n}$ and $G_{1} (s) \in {0, 1}$ . Define $G^{(k)}$ inductively: $G^{(1)} (s) = G_{1} (s)$ , $G^{(k)} (s) = G^{(k - 1)} (G_{0} (s)) ∥ G_{1} (G_{0}^{(k - 1)} (s))$ .

The output length is $n + k$ bits: $n$ bits from the final state plus $k$ extracted bits. A hybrid argument shows indistinguishability: if a distinguisher $D$ can tell $G^{(k)} (U_{n})$ from $U_{n + k}$ , then by the hybrid argument over $k$ intermediate hybrids, at least one pair of consecutive hybrids is distinguishable, which gives a distinguisher for the original PRG $G$ . Since $G$ is secure, no such distinguisher exists, so $G^{(k)}$ is also a PRG. Setting $k = n^{c} - n$ gives polynomial stretch.

Exercise 4 (medium, symbolic).

Prove the next-bit unpredictability characterisation: $G$ is a PRG if and only if no PPT algorithm can predict bit $b_{i + 1}$ given $b_{1}, \dots, b_{i}$ with probability better than $1/2 + negl (n)$ .

Answer

Forward direction. If a predictor $P$ predicts bit $i + 1$ with advantage $ε$ , construct a distinguisher $D$ for $G$ : on input $y = b_{1} \dots b_{n}$ , check if $P (b_{1} \dots b_{i}) = b_{i + 1}$ . If so output 1, else output 0. On pseudorandom inputs (from $G$ ), $D$ outputs 1 with probability $1/2 + ε$ . On random inputs, $D$ outputs 1 with probability $1/2$ (since $b_{i + 1}$ is uniform and independent of $b_{1}, \dots, b_{i}$ ). So $D$ distinguishes with advantage $ε$ , contradicting PRG security.

Backward direction (Yao's theorem). If $D$ distinguishes $G (U_{s})$ from $U_{n}$ with advantage $ε$ , construct a hybrid argument. Define $H_{i}$ as the distribution where the first $i$ bits come from $G (U_{s})$ and the remaining $n - i$ bits are uniform. Then $H_{0} = U_{n}$ and $H_{n} = G (U_{s})$ . Since $D$ distinguishes $H_{0}$ from $H_{n}$ with advantage $ε$ , by averaging, some pair $H_{i}, H_{i + 1}$ is distinguished with advantage $ε / n$ . This gives a predictor for bit $i + 1$ : guess bit $i + 1$ uniformly, then run $D$ on the hybrid string and use its output to correct the guess.

Exercise 6 (hard, symbolic).

Prove that if one-way functions exist, then there exist one-way functions with hard-core predicates (without assuming Goldreich-Levin).

Hint

Given a OWF $f$ , define $g (x, r) = (f (x), r)$ where $∣ x ∣ = ∣ r ∣$ . The hard-core predicate is $⟨ x, r ⟩$ .

Answer

Given a OWF $f : {0, 1}^{n} \to {0, 1}^{m}$ , define $g : {0, 1}^{2 n} \to {0, 1}^{m + n}$ by $g (x, r) = (f (x), r)$ where $∣ r ∣ = n$ . First, $g$ is a OWF: if $A$ inverts $g$ with non-negligible probability, then given $y = f (x)$ , choose a random $r$ and run $A$ on $(y, r)$ ; if $A$ returns $(x^{'}, r^{'})$ with $g (x^{'}, r^{'}) = (y, r)$ , then $r^{'} = r$ and $f (x^{'}) = y$ , so $x^{'} \in f^{- 1} (y)$ , inverting $f$ .

Now, by the Goldreich-Levin theorem, $h (x, r) = ⟨ x, r ⟩$ is a hard-core predicate for $g$ . Alternatively, without using GL: define $g^{'} (x, r) = (f (x), r)$ and $h (x, r) = x_{1}$ (the first bit of $x$ ). If $h$ were not hard-core, there would be an algorithm predicting $x_{1}$ from $(f (x), r)$ , but $r$ is independent of $x$ , so this gives no information about $x_{1}$ beyond what $f (x)$ provides. This argument does not always work because $f$ might leak $x_{1}$ . The Goldreich-Levin theorem is the correct and complete answer: it constructs a specific hard-core predicate (inner product with a random vector) and proves its unpredictability from the one-wayness of $f$ . Rubric: full credit for recognising that GL is the correct tool.

Exercise 7 (hard, symbolic).

Sketch the HILL construction: given any one-way function $f$ , construct a pseudorandom generator $G$ . Describe the high-level steps (weak OWF amplification, entropy extraction, PRG assembly).

Answer

The HILL construction has three stages:

Weak-to-strong amplification. If $f$ is a weak OWF (invertible with probability at most $1 - 1/ p (n)$ for polynomial $p$ ), then $F (x_{1}, \dots, x_{k}) = (f (x_{1}), \dots, f (x_{k}))$ for $k = O (n \cdot p (n))$ is a strong OWF. The proof uses a direct product argument: if an inverter succeeds on $F$ , it must succeed on all $k$ coordinates, and the probability of this decays exponentially.
From OWF to PRG via entropy extraction. Given a strong OWF $f$ , the output $f (x)$ has some computational entropy (it looks like it has more entropy than it actually does, to any polynomial-time algorithm). Using the Goldreich-Levin hard-core predicate as an entropy extractor, one can extract pseudorandom bits from the computational entropy of $f (x)$ . The key insight is that $f (x)$ has "hidden" entropy that can be unlocked by pairing it with a random $r$ and computing $⟨ x, r ⟩$ .
PRG assembly. Combine the extracted bits from multiple invocations of $f$ to produce a PRG with polynomial stretch. The final construction runs $f$ on multiple independent inputs, extracts hard-core bits from each, and concatenates them.

Rubric: full credit for describing the three stages and the role of the Goldreich-Levin predicate.

Exercise 8 (hard, symbolic).

Prove that OWFs exist if and only if PRGs exist. (One direction is given by the HILL theorem; prove the converse.)

Answer

PRG implies OWF. Let $G : {0, 1}^{n} \to {0, 1}^{n + 1}$ be a PRG. Define $f (x) = G (x)$ . Then $f$ is polynomial-time computable. Suppose for contradiction that $f$ is not one-way: there exists a PPT inverter $A$ that, given $y = G (x)$ , finds $x^{'}$ with $G (x^{'}) = y$ with non-negligible probability $ε$ .

We construct a distinguisher $D$ for $G$ : on input $y \in {0, 1}^{n + 1}$ , run $A (y)$ to get $x^{'}$ . If $G (x^{'}) = y$ , output 1 (pseudorandom). Otherwise output 0.

On pseudorandom inputs $y = G (x)$ for random $x$ : $D$ outputs 1 with probability $ε$ (the probability $A$ inverts successfully). On truly random inputs $y \in {0, 1}^{n + 1}$ : the fraction of $y$ in the image of $G$ is at most $2^{n} / 2^{n + 1} = 1/2$ , so even if $A$ always succeeds on image points, $D$ outputs 1 with probability at most $1/2$ .

If $ε > 1/2 + negl (n)$ , this distinguishes. For smaller $ε$ , the argument requires showing that $A$ 's success rate on pseudorandom inputs exceeds its success rate on random inputs by a non-negligible amount, which follows because the pseudorandom distribution is concentrated on the image of $G$ (size $2^{n}$ ) while the uniform distribution is spread over $2^{n + 1}$ elements. The distinguishing advantage is at least $ε - 1/2$ , contradicting PRG security.

Rubric: full credit for the reduction from PRG distinguisher to OWF inverter.

Lean formalization Intermediate+

Mathlib has no formalization of one-way functions, pseudorandom generators, or the Goldreich-Levin theorem. These are computational notions requiring probabilistic polynomial-time adversaries, security parameters, and negligible functions—none of which are in Mathlib's scope. The foundational gap is the absence of a ComputationalHardness framework that connects algorithmic complexity to security definitions. A formalization of the PRG-stretching lemma (Exercise 3) using Mathlib's existing probability and computation structures would be a natural starting point. This unit ships without a lean_module.

Advanced results Master

Three directions extend the OWF-PRG framework.

Result 1 (OWF implies PRG: the HILL theorem). Håstad, Impagliazzo, Levin and Luby (1999) proved that one-way functions exist if and only if pseudorandom generators exist. The harder direction (OWF implies PRG) proceeds via computational entropy: a OWF $f$ has the property that $f (U_{n})$ has high computational entropy (it looks like it has $n$ bits of entropy even if the true entropy is less). The Goldreich-Levin hard-core predicate extracts one pseudorandom bit from this computational entropy, and the PRG is assembled by concatenating extracted bits from multiple invocations. The construction is polynomial-time but with a large polynomial, making it theoretically important but impractical ^{[HILL 1999]}.

Result 2 (pseudorandom functions). A pseudorandom function (PRF) family ${f_{s} : {0, 1}^{n} \to {0, 1}^{n}}_{s \in {0, 1}^{n}}$ is a collection of functions indexed by a seed $s$ such that no PPT algorithm can distinguish oracle access to $f_{s}$ (for random $s$ ) from oracle access to a truly random function. Goldreich, Goldwasser and Micali (1986) showed that PRFs can be constructed from PRGs, and hence from OWFs. PRFs are the workhorse of symmetric cryptography: they yield encryption, MACs, and authenticated encryption ^{[Arora-Barak Ch. 9]}.

Result 3 (black-box separations). Impagliazzo and Rudich (1989) showed that there is no black-box reduction from key exchange (and hence from public-key cryptography) to one-way functions. This means that the construction of public-key primitives from OWFs, if possible at all, must use non-black-box techniques. This separation explains why the cryptographic landscape splits into symmetric primitives (from OWFs) and public-key primitives (from structured assumptions like factoring or discrete log) ^{[Arora-Barak Ch. 9]}.

Synthesis. The equivalence OWF $\Leftrightarrow$ PRG is the foundational result that unifies computational hardness and pseudorandomness: any function that is easy to compute but hard to reverse provides a source of pseudorandom bits, and this builds toward the full edifice of symmetric cryptography where PRGs yield PRFs, PRFs yield encryption and MACs, and all of it rests on the existence of one-way functions. The central insight is that the hardness of a single computational task (inverting $f$ ) is sufficient to bootstrap the entire cryptographic toolkit, and this is exactly the pattern that appears again in 47.06.02 where specific number-theoretic OWFs give concrete instantiations. Putting these together with the derandomisation perspective of 47.05.05 shows that the same pseudorandomness phenomenon serves dual purposes: in complexity theory it enables derandomisation (BPP = P conjectured), and in cryptography it enables secure communication (OWF implies PRG proven).

Full proof set Master

Proposition 1 (Goldreich-Levin: prediction implies inversion). If there exists a PPT algorithm $A$ with $Pr_{x, r} [A (f (x), r) = ⟨ x, r ⟩] \geq 1/2 + ε$ for non-negligible $ε$ , then there exists a PPT algorithm $B$ that inverts $f$ with probability $Ω (ε^{2} / n)$ .

Proof. The algorithm $B$ , given $y = f (x)$ , recovers $x$ as follows:

For each $i \in [n]$ and each candidate bit $b \in {0, 1}$ , estimate:

p_{i}^{b} = r Pr [A (y, r) = ⟨ x, r ⟩ ∣ r_{i} = b] .

Since $A$ predicts $⟨ x, r ⟩$ with advantage $ε$ on average over $r$ , by a hybrid argument over the bits of $r$ , for a $2 ε$ -fraction of inputs $x$ , the predictor $A$ has advantage $ε$ conditioned on any fixed prefix of $r$ .

For such an $x$ , the self-correction trick gives: $x_{i} = ⟨ x, e_{i} ⟩ = Pr_{r} [A (y, r) = A (y, r \oplus e_{i})]$ (approximately). By sampling $O (n / ε^{2})$ random values of $r$ for each pair $(r, r \oplus e_{i})$ and taking majority, $B$ recovers each bit $x_{i}$ with high probability.

The probability of correct inversion is at least $2 ε \cdot (1 - 1/3 n)^{n} \geq ε$ (the $2 ε$ fraction of good $x$ times the probability all $n$ bits are recovered correctly). Running time is $O (n^{2} / ε^{2})$ per input. $□$

Proposition 2 (PRG from one-way permutation). If $f : {0, 1}^{n} \to {0, 1}^{n}$ is a one-way permutation and $h$ is a hard-core predicate for $f$ , then $G (x, r) = (f^{(1)} (x), \dots, f^{(n)} (x), h (x, r), h (f (x), r), \dots, h (f^{(n - 1)} (x), r))$ is a PRG mapping $2 n$ bits to $2 n + n = 3 n$ bits.

Proof sketch. Since $f$ is a permutation, $f^{(i)} (U_{n}) = U_{n}$ for all $i$ , so the first $n^{2}$ bits of the output are uniformly random. For each output bit $b_{i} = h (f^{(i)} (x), r)$ : since $f^{(i)} (x)$ is uniformly random (as $f$ is a permutation), the pair $(f^{(i)} (x), r)$ has the same distribution as $(x^{'}, r)$ for uniform $x^{'}$ and $r$ . By the hard-core property of $h$ , no PPT algorithm can predict $b_{i}$ from $(f^{(i + 1)} (x), r)$ (which is $(f (f^{(i)} (x)), r)$ ) with non-negligible advantage.

A hybrid argument over the $n$ extracted bits shows that the entire output is pseudorandom: any distinguisher for $G$ must distinguish at least one hybrid from the next, giving a predictor for the corresponding hard-core bit, contradicting the hard-core property. $□$

Connections Master

47.02.01 — P vs NP is the prerequisite: if P = NP then one-way functions do not exist, and all of cryptography collapses.
47.05.05 — Derandomisation uses PRGs to replace randomness in algorithms; cryptographic PRGs must fool all efficient adversaries, while derandomisation PRGs only need to fool specific tests.
47.06.02 — RSA and discrete logarithm provide concrete candidate one-way functions and hard-core predicates, instantiating the abstract framework defined here.
47.06.03 — Zero-knowledge proofs require commitment schemes built from one-way functions; the OWF-implies-PRG theorem is the first step in the construction chain.
47.06.04 — Digital signatures require trapdoor one-way functions (a stronger notion than plain OWFs); collision-resistant hash functions provide another cryptographic primitive built from hardness assumptions.

Historical & philosophical context Master

The concept of one-way functions emerged from Diffie and Hellman's 1976 paper "New Directions in Cryptography," which proposed that computational hardness could serve as the basis for secure communication. The formal definition was given by Yao (1982) in his paper on pseudorandom generation.

The Goldreich-Levin theorem (1989) is a cornerstone of cryptography, establishing that every one-way function has a hard-core predicate. The proof uses Fourier analysis over the Boolean hypercube, connecting cryptography to algebraic techniques. The HILL theorem (1999) completed the picture by showing that OWFs and PRGs are equivalent.

The philosophical significance is profound: randomness, secrecy, and computational hardness are three faces of the same coin. A function that is hard to invert is simultaneously a source of pseudorandomness and a mechanism for hiding information. The OWF-PRG equivalence is the formal expression of this trinity ^{[Arora-Barak Ch. 9]}.

Bibliography Master

@book{arora2009computational,
  author    = {Arora, Sanjeev and Barak, Boaz},
  title     = {Computational Complexity: A Modern Approach},
  publisher = {Cambridge University Press},
  year      = {2009},
}
@article{goldreich1989hard,
  author  = {Goldreich, Oded and Levin, Leonid A.},
  title   = {A Hard-Core Predicate for All One-Way Functions},
  journal = {Proceedings of the 21st ACM Symposium on Theory of Computing},
  year    = {1989},
  pages   = {25--32},
}
@article{hastad1999pseudorandom,
  author  = {H{\aa}stad, Johan and Impagliazzo, Russell and Levin, Leonid and Luby, Michael},
  title   = {A Pseudorandom Generator from any One-Way Function},
  journal = {SIAM Journal on Computing},
  volume  = {28},
  number  = {4},
  pages   = {1364--1396},
  year    = {1999},
}
@article{blum1982secure,
  author  = {Blum, Manuel and Micali, Silvio},
  title   = {How to Generate Cryptographically Strong Sequences of Pseudorandom Bits},
  journal = {SIAM Journal on Computing},
  volume  = {13},
  number  = {4},
  pages   = {850--864},
  year    = {1984},
}

Prerequisites

47.02.01

Tier anchors

beginner: Arora and Barak 2009 Computational Complexity: A Modern Approach (Cambridge) Ch. 9 (functions that are easy to compute but hard to invert, and how they generate randomness)
intermediate: Arora and Barak 2009 Computational Complexity: A Modern Approach (Cambridge) Ch. 9 (formal OWF definition, PRG construction via Blum-Micali-Yao, next-bit unpredictability, IND-CPA security)
master: Arora and Barak 2009 Computational Complexity: A Modern Approach (Cambridge) Ch. 9; Håstad, Impagliazzo, Levin and Luby 1999 A Pseudorandom Generator from any One-Way Function (SIAM J. Comput.) (HILL construction: OWF implies PRG)

References

Arora, S. and Barak, B. — Computational Complexity: A Modern Approach · Cambridge University Press (2009). Chapter 9 develops one-way functions and pseudorandom generators, defining a one-way function $f : {0, 1}^{*} \to {0, 1}^{*}$ as a polynomial-time computable function such that for every probabilistic polynomial-time algorithm $A$ , $Pr_{x \in {0, 1}^{n}} [A (f (x)) \in f^{- 1} (f (x))] \leq negl (n)$ where $negl (n)$ is a function vanishing faster than any polynomial fraction; a pseudorandom generator $G : {0, 1}^{s} \to {0, 1}^{n}$ with stretch $n > s$ satisfies that no polynomial-time algorithm distinguishes $G (U_{s})$ from $U_{n}$ with advantage more than $negl (n)$ ; the Blum-Micali-Yao construction builds a PRG from any one-way permutation $f$ using the Goldreich-Levin hard-core predicate $h (x, r) = ⟨ x, r ⟩$ , iterating $f$ and extracting one pseudorandom bit per step via $b_{i} = h (f^{(i)} (x), r_{i})$ to stretch $n$ bits to $n + n^{c}$ bits.
Håstad, J., Impagliazzo, R., Levin, L. and Luby, M. — A Pseudorandom Generator from any One-Way Function · SIAM Journal on Computing 28(4):1364--1396 (1999). Proves that pseudorandom generators exist if and only if one-way functions exist; the construction transforms any weak one-way function (invertible with probability at most $1 - 1/ q (n)$ for some polynomial $q$ ) into a strong one-way function via sequential composition, then into a pseudorandom generator using the hidden number theorem and the Goldreich-Levin hard-core predicate extraction; the stretch is polynomial in the seed length.

Estimated time

beginner: 15m
intermediate: 40m
master: 90m