Motivation
A concept class can consist of efficiently evaluable functions and still resist efficient learning. Evaluation is a task performed with a secret key; learning is a task in which the key is hidden and the learner sees examples. Pseudorandom functions formalize a particularly strong separation: without the key, even an algorithm that chooses polynomially many inputs cannot reliably distinguish the keyed function from a uniformly random function.
If an efficient PAC learner could predict every function in such a family from random examples, its predictor would behave differently on a keyed function and a random function. That difference can be converted into an oracle distinguisher. The argument is conditional on a precise pseudorandom-function assumption. It does not prove unconditional computational hardness, and it does not say that every cryptographic construction is hard to learn.
The two computational models
Definition 10.1.1
(An efficiently computable pseudorandom-function family)
For each security parameter , let and let keys be uniform in , where is a polynomial. The family consists of deterministic functions
computed by one algorithm in time polynomial in . An oracle distinguisher receives , may adaptively query a function at inputs of its choice, and outputs one bit. It is probabilistic polynomial-time if its runtime, including oracle calls, is polynomial in .
The family is pseudorandom if, for every such , the absolute difference between its probabilities of outputting one in the following two experiments is negligible in :
- Keyed experiment: draw one uniform key and answer every query using the same function .
- Random-function experiment: draw one uniformly random function and answer every query using that same .
A nonnegative function is negligible if, for every positive polynomial , eventually . In the random-function experiment, values on distinct inputs are independent fair bits, but repeating an input repeats its earlier answer. Equivalently, one can assign a fresh fair bit on the first query to each input and remember it thereafter.
The random function is an ideal oracle, not a polynomial-size table supplied to the distinguisher. For any polynomial number of calls its answers can be simulated lazily. The indistinguishability assumption quantifies over adaptive distinguishers, a stronger access model than random labeled examples. The reduction below uses only independently sampled uniform query points, so security against polynomially many such random queries would already suffice for its contradiction. The key and the random function are each drawn once per experiment, not independently for each query.
Definition 10.1.2
(Efficient distribution-free PAC learning)
Let . A distribution-free PAC learner receives , accuracy and failure parameters , and access to independent labeled examples for an arbitrary distribution on and target . It outputs a Boolean hypothesis such that
Efficient means worst-case runtime and number of requested examples are polynomial in , uniformly over all inputs and random choices, and the output representation can be evaluated in polynomial time. The learner need not output a member of : improper hypotheses are allowed.
The outer probability concerns the training data and learner randomness; the inner probability is the population error of the resulting hypothesis. The guarantee is required for every target and every input distribution. We will use it only at the uniform distribution, so the proof actually rules out the stated kind of efficient learner even for a learner required to succeed only on that fixed uniform distribution; the learner may be told the distribution.
The reduction theorem
Lemma 10.1.3
(Fresh-test bound for a random function)
Let be uniformly random. An algorithm makes at most oracle queries, possibly adaptive and repeated, and produces an efficiently evaluable Boolean predictor based on its transcript and randomness. If is then drawn independently and uniformly, its probability of matching is at most
This is an information bound; it remains valid even without the efficiency requirement. The proof is to condition on the transcript: unseen random-function values remain independent fair bits, while the chance that belongs to the at-most- queried points is at most .
Theorem 10.1.4
(Pseudorandomness excludes an efficient learner)
Assume the Boolean family above is pseudorandom against every probabilistic polynomial-time oracle distinguisher. Then there is no efficient distribution-free PAC learner for in the stated model. In fact, no such learner can satisfy the PAC guarantee for the uniform distribution alone, even if it outputs efficiently evaluable hypotheses outside the class.
The theorem is a conditional implication. It does not assert that a particular keyed algorithm is pseudorandom merely because its key is hidden, nor does it establish the existence of the assumed family unconditionally.
Constructing the distinguisher
Proof
(Train, then test at an independent point)
Suppose such a learner exists. Fix . Its runtime and example count are then bounded by some polynomial , uniformly over its inputs and random choices. The distinguisher has access to an unknown oracle , which is either or .
Whenever requests a labeled example, draws a fresh uniform , queries and returns . The draws are independent and may repeat. When outputs its efficiently evaluable hypothesis , the distinguisher draws one more independent uniform point , queries , and outputs one exactly when . The simulation, including this evaluation and oracle call, runs in probabilistic polynomial time.
In the keyed experiment, condition on any key . The simulated examples are i.i.d. uniform examples labeled by , so the PAC guarantee applies. With probability at least the returned hypothesis has error at most under the uniform distribution. Conditional on such a hypothesis, the independent test point is correctly labeled with probability at least . Therefore
This lower bound holds for each key before averaging over the random key. On training runs that do not meet the PAC guarantee, the acceptance probability is nonnegative; no additional claim about them is needed.
In the random-function experiment, let be the set of distinct training inputs. Conditional on the transcript and learner's randomness, and are fixed. If , the value is a fresh independent fair bit, so the conditional agreement probability is exactly . If , agreement can be as large as one. Since and is independent uniform,
Hence
The distinguisher's advantage is at least . Since is polynomial, eventually and the advantage is at least . A quantity at least for all sufficiently large is not negligible, contradicting pseudorandomness and proving the theorem.
Proof X-ray
The collision term is part of the reduction
A truly random function remembers its answer at an input. The test label is an independent fair bit only when the test input was not used during training. Bounding the probability of that collision is what makes the comparison valid on a finite domain. The key case uses PAC generalization; the random-function case uses fresh-point independence; efficient hypothesis evaluation makes the resulting distinguisher polynomial-time.
The sample budget need not be exactly . If the learner chooses when to stop based on previous examples, its number of calls is still at most the polynomial bound and the test point is drawn after training. Conditioning on the full transcript gives the same estimate. We do not need to condition on all training inputs being distinct: repeated training inputs merely reduce .
Worked examples
Worked example 10.1.5
(A finite-domain advantage calculation)
Suppose and the learner requests at most examples. The random-function acceptance probability in the reduction is at most
The keyed acceptance probability is at least , so the difference is at least about . These are bounds, not exact acceptance probabilities. The asymptotic contradiction uses a polynomial for all sufficiently large , not one numerical parameter value alone.
Worked example 10.1.6
(Why the same random function must remember)
On the two-point domain , suppose one training input and one independent test input are uniform. Let a predictor memorize the observed label, use it if the test input repeats, and otherwise guess a fair bit. The test collides with probability , so its agreement probability with a uniformly random function is
Calling every test label an independent fair bit would incorrectly predict agreement . The general bound gives here. At large with polynomially many samples, the collision contribution vanishes, but it is not identically zero at finite .
Worked example 10.1.7
(The reduction does not require a proper hypothesis)
A learner might output a circuit that is not equal to for any key . The distinguisher still evaluates that circuit at and compares the result with the oracle. Its proof uses only the PAC error guarantee and efficient evaluation, never a procedure to recover a key. Recovering the secret key is therefore unnecessary for this contradiction; prediction on fresh points is enough.
Counterexample mode
A hidden key does not automatically give pseudorandomness
Let for . This is efficiently computable and has a hidden key, but for every key. A distinguisher queries once and outputs one if the answer is zero. Its acceptance probability is one in the keyed experiment and for a uniformly random function, giving advantage . The family fails the stated pseudorandomness assumption. This parity family is also efficiently learnable from uniform labeled examples by binary linear algebra; that does not contradict the theorem because the family fails the PRF assumption. A secret parameter alone is not a security proof.
Common mistakes
Common mistake
(Replacing a random function by independent labels at repeated inputs)
Independent fair labels are correct on previously unseen inputs of a random function, but not on repeated inputs. Use the collision event, or deliberately sample test points outside the training set and analyze the resulting change of distribution. The proof above keeps the test point uniform and pays an explicit collision term.
Common mistake
(Overstating a conditional reduction)
The conclusion assumes an efficiently computable family satisfying oracle pseudorandomness. It does not prove that such a family exists without assumptions, nor that a particular implementation is secure. It also relies on the learner's output being efficiently evaluable: otherwise the proposed distinguisher may not run in polynomial time.
Summary
A uniform-distribution PAC predictor for every keyed function would distinguish a pseudorandom function from a truly random function by testing one fresh random input. The predictor succeeds often in the keyed experiment; a random function is unpredictable at an unseen point, up to an explicit finite-domain collision probability. Thus oracle pseudorandomness conditionally rules out efficient learning in the stated model, even with improper hypotheses.
Exercises
Quick check
(In the random-function experiment with and at most training examples, use the proof to bound the probability that the one-point test accepts.)
Use the bound .
Solution · Answer
The proof gives . The actual value depends on the learner and on repeated training points; the expression is an upper bound.
Quick check
(Repeat the reduction with and . Give a lower bound on keyed acceptance and on the distinguishing advantage in terms of and .)
Multiply the probability that the hypothesis is good by the probability that the test point is labeled correctly.
Solution · Answer
Keyed acceptance is at least . Random-function acceptance is at most , so the advantage is at least . When is polynomial this is positive and nonnegligible for sufficiently large .
Quick check
(A proposed simulator answers each repeated oracle query with a new independent fair bit. Give a two-query distinguisher showing that this is not the random-function experiment.)
A random function remembers its answers.
Solution · Answer
Query the same input twice and output one if the two answers agree. For one random function they always agree; for independently regenerated fair bits they agree with probability . The acceptance difference is .
Quick check
(For the keyed parity family , calculate the one-query advantage of the zero-input distinguisher and explain what assumption it violates.)
Evaluate every keyed function at .
Solution · Answer
The keyed answer at is always zero, while a random function's value there is a fair bit. Accepting when the answer is zero gives probabilities one and , hence advantage . This family is not pseudorandom against the permitted oracle distinguishers.