💻 computer science

Lower Bounds on Black-Box Constructions of Pseudorandom Functions

This paper establishes that no fully black-box construction of a pseudorandom function (PRF) from a pseudorandom generator (PRG) can achieve $o(n/\log n)$ non-adaptive calls to the PRG, even for weak PRFs with one-bit outputs, thereby providing strong lower bounds on the efficiency of such constructions and leaving the possibility of a single-invocation construction as a major open challenge.

Original authors: Bar Alon, Itai Dinur, Muthuramakrishnan Venkitasubramaniam

Published 2026-08-17

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Bar Alon, Itai Dinur, Muthuramakrishnan Venkitasubramaniam

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Digital Locksmith's Dilemma

Imagine you are a master locksmith trying to build an unbreakable vault door. In the world of digital security, this "vault" is a Pseudorandom Function (PRF). Think of a PRF as a magical machine: you feed it a secret key and a specific input (like a room number), and it spits out a string of numbers that looks completely random to anyone watching. However, if you use the same secret key again, it always produces the exact same "random" string. This consistency is what makes it useful for locking down your emails, securing your bank transactions, and keeping your passwords safe.

To build this magical machine, cryptographers often start with something simpler called a Pseudorandom Generator (PRG). A PRG is like a tiny, efficient seed that grows into a massive, random-looking forest. It takes a short, secret string and stretches it into a much longer one that looks random to any computer program. The big question in cryptography has been: How many times do we need to use this "seed-stretching" machine to build our "vault door"?

For decades, the standard recipe (known as the GGM construction) has been to use the seed-stretching machine over and over again, in a tree-like structure, roughly $\omega(\log n)$ times (where $n$ is the size of the seed). It works great, but it feels a bit clunky. Is there a shortcut? Could we build a perfect vault door by using the seed-stretching machine just once? Or maybe just a handful of times? This paper dives deep into that question, acting like a detective trying to prove that no matter how clever you are, you simply cannot build a secure vault door with too few stretches of the seed.

The Paper's Big Discovery: The "Too Few" Problem

This paper, written by Bar Alon, Itai Dinur, and Muthuramakrishnan Venkitasubramaniam, tackles the fundamental question: What is the absolute minimum number of times we must call a Pseudorandom Generator (PRG) to build a Pseudorandom Function (PRF)?

The authors prove that for a specific and very reasonable type of construction, the answer is "a lot more than you might hope." Specifically, they show that you cannot build a secure PRF using a "fully black-box" method if you only call the PRG a tiny number of times—specifically, fewer than roughly $n / \log n$ times (where $n$ is the length of the PRG's input).

To understand their proof, imagine a game of "Spot the Fake."

The Setup: A "Reduction" (the builder) tries to create a PRF using a PRG. They also have an "Adversary" (a hacker) trying to tell if the PRF is real or just a random function.
The Trick: The authors imagine a scenario where the builder is "query-bounded." This means the builder can ask the hacker for help, but the number of times they can ask is limited and doesn't explode based on how many questions the hacker asks.
The Counter-Attack: The authors construct a "Real Adversary" and an "Ideal Adversary."
- The Ideal Adversary is a super-powerful, slow computer that can check every possible secret key to see if it fits the data. It can easily tell if a function is a PRF or random.
- The Real Adversary is the one the builder actually uses. It doesn't have superpowers; it only sees the limited questions the builder asked the PRG.
The Reveal: The authors prove that if the builder uses too few calls to the PRG, the "Real Adversary" can perfectly mimic the "Ideal Adversary" without actually breaking the PRG's security. This creates a paradox: if the builder could build a secure PRF with so few calls, they would also be able to break the PRG itself using a method that is too slow to be practical, which contradicts the assumption that the PRG is secure.

The Main Result:
The paper proves that for non-adaptive constructions (where the builder decides all the PRG questions before seeing any answers), it is impossible to build a PRF with fewer than $o(n / \log n)$ calls to the PRG. This holds true even if the PRF only outputs a single bit (a 0 or 1) and even if the hacker is restricted to asking simple, random questions.

The "Long Output" Result:
The authors also looked at PRFs that produce long strings of data (not just one bit). They proved that even if the builder is allowed to be "adaptive" (asking questions one by one and using the answers to decide the next question), there is still a hard limit. If the PRG stretches the input by a small amount, you need at least roughly $out / \log n$ calls. If the PRG stretches it by a large amount, you need at least $out / r$ calls.

What This Means for the "One Call" Dream

For a long time, cryptographers wondered if a "single-call" construction was possible—building a perfect PRF by stretching the seed just once.

For non-adaptive methods: This paper effectively rules it out. You cannot build a secure PRF with a constant number of calls (like 1, 2, or 10) if the input size grows. The math simply doesn't allow it.
For adaptive methods: The paper does not rule out a single-call construction for all adaptive scenarios. Instead, it shows that for PRFs with long outputs, the number of calls must scale with the output size. You can't just get away with a tiny, fixed number of calls for a massive vault door if the output is large. The question of whether a single-call adaptive construction exists for PRFs with short outputs remains open.

The "Query-Bounded" Caveat

The authors are very careful about their assumptions. They focus on a class of reductions they call "query-bounded." In plain English, this means the builder's interaction with the hacker is limited in a way that doesn't depend on how many questions the hacker asks. The authors argue that almost every construction in the history of cryptography fits this description. They acknowledge that if someone invents a weird, non-standard way of building a PRF where the builder asks the hacker millions of times just because the hacker asked one question, their proof might not apply. But for all practical, standard cryptographic designs, the lower bounds they found hold firm.

The Takeaway

This paper doesn't just suggest a limit; it provides a mathematical proof that the "shortcut" to building PRFs is a dead end. If you want a secure, black-box PRF, you cannot skip the steps. You have to pay the cost of calling the PRG enough times to ensure that the "entropy" (the randomness and unpredictability) is high enough to fool any hacker. The famous GGM construction, which uses about $\omega(\log n)$ calls, turns out to be nearly optimal. The dream of building a fortress with a single brick is mathematically impossible in this context.

Technical Summary: Lower Bounds on Black-Box Constructions of Pseudorandom Functions

Problem Statement

The paper addresses a fundamental open question in cryptography: What is the minimal number of invocations of a pseudorandom generator (PRG) required to construct a pseudorandom function (PRF) via a fully black-box construction?

The seminal work of Goldreich, Goldwasser, and Micali (GGM) established that a PRF can be constructed from a PRG using a tree-based approach. When combined with Levin's domain extension technique, this construction requires $\omega(\log n)$ calls to the PRG, where $n$ is the PRG's input length. While recent work by Beimel, Malkin, and Mazor proved the optimality of GGM for a specific class of "tree constructions," the general case remains unresolved. Specifically, it is unknown whether a PRF can be built with fewer than $\omega(\log n)$ calls, or even with a single call, using general black-box techniques.

This work investigates this question within the framework of fully black-box constructions, where both the construction and the security reduction are black-box. The authors specifically focus on a class of reductions termed query-bounded reductions, where the number of interactions the reduction makes with the adversary is upper-bounded by a polynomial independent of the adversary's query complexity (provided the adversary is sufficiently successful).

Methodology

The authors employ the meta-reduction paradigm to establish their lower bounds. This technique involves constructing an inefficient "real" adversary that can simulate an "ideal" adversary (which breaks the PRF) without direct access to the underlying PRG, thereby breaking the PRG's security using fewer queries than allowed.

Key Technical Components:

Query-Bounded Reductions: The authors define a reduction as query-bounded if the number of times it queries the distinguishing adversary is bounded by a polynomial $d(n)$ , regardless of how many queries the adversary makes to its oracle. This class captures most known reductions in the literature, including GGM and Goldreich-Levin constructions.
Ideal vs. Real Adversaries:
- Ideal Adversary ( $A_{ideal}$ ): An inefficient adversary that has exponential access to the PRG oracle. It attempts to break the PRF by finding a key consistent with a large fraction of input-output pairs.
- Real Adversary ( $A_{real}$ ): An inefficient adversary that does not have access to the PRG. Instead, it receives the query-answer pairs generated by the reduction's interaction with the PRG. It attempts to simulate $A_{ideal}$ by estimating the probability that a key is consistent with the observed outputs.
Score Functions and Independence:
- The core challenge is that the outputs of the PRF on different inputs may be dependent if they share PRG seeds.
- The authors introduce a procedure to identify "frequent seeds" (seeds used by many inputs) and replace their outputs with fixed values. This reduces the number of active PRG calls.
- For the remaining inputs, they utilize a combinatorial claim (Claim 3/6) to show that either a large set of inputs uses mutually disjoint PRG seeds (allowing for independence arguments via Hoeffding's inequality) or the number of such keys is negligible.
- To handle the statistical distance between the ideal and real adversaries, the authors use a randomized threshold (sampled uniformly from $[0.8, 1]$ ) rather than a fixed threshold. This smooths the decision boundary, ensuring that the real adversary's output distribution is statistically close to the ideal adversary's, provided the number of inputs $m$ is sufficiently large relative to the number of reduction queries $d$ .
Entropy Arguments for Long Outputs: For the second result (Theorem 2), the authors use an entropy-based argument. They construct a specific PRG that applies randomness only to a small prefix of the seed. This limits the entropy of the PRF output to be significantly lower than that of a truly random function, allowing a distinguisher to break the construction if the number of calls is too low.

Key Contributions and Results

1. Lower Bound for Non-Adaptive Calls (Theorem 1)

The paper proves that no fully black-box construction of a PRF from a PRG exists using non-adaptive calls and query-bounded reductions if the number of calls $c$ satisfies:
$c = o\left(\frac{n}{\log n}\right) \quad \text{and} \quad c = o\left(\frac{in}{\log in}\right)$
where $n$ is the PRG input length and $in$ is the PRF input length.

Scope: This result holds even for weak PRFs (where the adversary is restricted to i.i.d. uniform queries) and for PRFs with one-bit output.
Implication: This rules out the possibility of constructing a PRF with a constant number of non-adaptive calls (e.g., a single call) for PRFs with input lengths $in = \omega(\log n)$ , resolving a specific case of the open problem for query-bounded reductions.

2. Lower Bound for Long Outputs (Theorem 2)

The paper establishes a lower bound for PRFs with long outputs ($out$) that holds even for adaptive constructions and does not require the reduction to be query-bounded.

Result: There is no fully black-box construction of a PRF with output length $out$ from a PRG with stretch $r$ using fewer than $\frac{out}{\max(r, \omega(\log n))}$ calls.
Comparison to GGM: The GGM construction (with Levin's trick) uses $\omega(\log n)$ calls to an $n$ -bit stretch PRG to produce an $n$ -bit output. By composing this with a 1-bit stretch PRG (requiring $O(n/\log n)$ calls), the total calls to a 1-bit stretch PRG is $\omega(n)$ . Theorem 2 implies a lower bound of $\Omega(n / \omega(\log n))$ , showing that GGM is optimal up to a factor of $\omega(\log n)$ .

Significance and Claims

The paper claims to make significant progress on the long-standing question of the optimality of PRF constructions from PRGs.

Optimality of GGM: While previous results were limited to "tree constructions," this work provides lower bounds for general black-box constructions under specific but natural assumptions (query-bounded reductions).
Resolution of the Single-Call Case: The authors explicitly state that their result resolves the question of whether a PRF can be built with a single call to the PRG for the class of query-bounded reductions. They demonstrate that such a construction is impossible for PRFs with input lengths $in = \omega(\log n)$ .
Robustness: The impossibility results hold even for weak PRFs and, in the case of long outputs, for adaptive constructions.
Limitations: The authors modestly acknowledge that their main result (Theorem 1) relies on the "query-bounded" assumption. They note that it remains an open question whether these lower bounds can be extended to all black-box reductions, as their proof relies on the reduction's interaction count being independent of the adversary's query complexity.

In summary, the paper demonstrates that the GGM construction is nearly optimal in terms of the number of PRG invocations required, particularly for non-adaptive constructions and those with long outputs, by leveraging meta-reduction techniques and careful entropy analysis.