Lower Bounds on Black-Box Constructions of Pseudorandom Functions

Lower Bounds on Black-Box Constructions of Pseudorandom Functions Bar Alon1∗ , Itai Dinur2,3 , and Muthuramakrishnan Venkitasubramaniam3 alonbar08@gmail.com, dinuri@bgu.ac.il, mv783@georgetown.edu 1

School of Electrical Engineering, Tel-Aviv University. Department of Computer Science, Georgetown University 3 Department of Computer Science, Ben-Gurion University

arXiv:2608.14501v1 [cs.CR] 14 Aug 2026

2

Abstract. In their seminal work, Goldreich, Goldwasser, and Micali [CRYPTO 1984] constructed a pseudorandom function (PRF) using a black-box access to a pseudorandom generator (PRG). When combined with Levin’s domain extension technique, the GGM construction invokes the PRG ω(log n) times, where n denotes the input length to the PRG. To this day, no black-box construction achieving fewer calls is known. Recently, Beimel, Malkin, and Mazor [CRYPTO 2024] showed that for a certain family of constructions, which they termed tree constructions, the GGM construction is optimal. However, the basic challenge of whether a PRF can be built with just one invocation of the PRG still remains open. In this work, we consider fully black-box constructions of PRFs from PRGs, where both the construction and the reduction are required to be black-box, and the number of interactions the reduction makes with the adversary is independent of the number of oracle calls the adversary makes to its underlying function within each interaction. Our main result shows that no such construction can have o(n/ log n) and o(in/ log in) non-adaptive calls to the PRG, where in is the input length of the PRF. This impossibility holds even for weak PRFs with one-bit output, where the adversary is restricted to making i.i.d. uniformly random queries. In addition, we prove a lower bound for weak PRFs with sufficiently long outputs that holds even when the construction is allowed to make adaptive queries to the PRG.

1

Introduction

A pseudorandom function (PRF) family is a collection of functions that appear random to any efficient algorithm. PRFs are fundamental to cryptography, both in theory and in practice, and have found many applications in areas outside of cryptography, such as in complexity and learning theory. The seminal work of Goldreich, Goldwasser, and Micali [10] (henceforth the GGM construction) shows that a PRF can be constructed from any pseudorandom generator – an efficient algorithm that on a random input, outputs a longer ∗

Work was conducted while at Georgetown University.

string that appears random to any efficient algorithm. Specifically, they showed that given black-box access to a pseudorandom generator (PRG) G : {0, 1}n →  2n {0, 1} , one can construct a PRF F = fk : {0, 1}in(n) → {0, 1}n k∈{0,1}n for any polynomial in(n). The number of calls to G in the GGM construction is |x| for any input x. A variant of the GGM construction that relies on Levin’s domain extension technique [13] improves the number of calls to ω(log n).4 However, a fundamental question has remained open since it was first discovered—is the construction optimal in the number of PRG invocations? More precisely, the following remains open: What is the minimal number of invocations of a (length-doubling) PRG required to build a PRF? Recently, Beimel et al. [2] made progress in answering this question. For a limited class of constructions that they refer to as tree constructions and generalizes the GGM construction, they prove that the GGM construction is optimal. In fact, their result holds even when considering PRFs with one-bit output. However, the state of affairs for more general (i.e. not necessarily tree) constructions, still remains open. In fact, previous results do not rule out the possibility of building a PRF with a single call to the PRG. 1.1

Our Results

We take a step towards answering the above question. We show two results. Our first and main result considers the already challenging setting of designing PRFs via non-adaptive calls to the underlying PRG (i.e., the construction generates all of its queries to the PRG before sending them). We demonstrate a lower bound on the number of calls to the underlying PRG oracle required for a fully black-box construction of a PRF. The impossibility is for a class of black-box reductions, which we call query-bounded reductions, which we define below. For our second result, we provide a lower bound for PRFs with a long output, which additionally includes adaptive constructions. Lower bounds for black-box constructions with non-adaptive calls. Our main result demonstrates the impossibility of building a PRF with input length in from a PRG with an arbitrary polynomial stretch, using c non-adaptive calls, where c = o(n/ log n) and c = o(in/ log in) via a fully black-box construction. We demonstrate this impossibility for a class of black-box reductions, which we call query-bounded reductions. Roughly, a reduction is query-bounded if the number of interactions it makes with the adversary is upper-bounded by a polynomial that is independent of the adversary’s query complexity (for all sufficiently successful adversaries). Recall that in the PRF setting, the adversary has access to a function oracle that it may call a bounded number of times. We focus on reductions whose number of 4 The final construction adds to the key a hash h : {0, 1}in(n) → {0, 1}ω(log n) from pair-wise independent hash function family, and applies the GGM construction to h(x).

2

interactions with the adversary may depend on the adversary’s success probability, but is independent of the number of oracle calls the adversary makes to the underlying function within each interaction. We believe this is a natural class of reductions and captures all reductions in the literature (see Section 2.1.3). In particular, it includes reductions whose number of interactions with the adversary decreases as the adversary’s success probability increases. It is an intriguing question whether one could extend the lower bound to all black-box reductions. Theorem 1 (Informal, impossibility for fully black-box construction). There is no fully black-box construction of a PRF with input length in from a PRG using query-bounded reductions and c non-adaptive calls, where c = o(n/ log n) and c = o(in/ log in). The formal statement and proof of Theorem 1 appear in Section 4. A few notes are in place. First, our proof works even for weak PRFs, where the adversary can only make i.i.d. uniform queries to the oracle. Second, unlike our second result (see Theorem 2 below), Theorem 1 holds for PRFs with one-bit output. Finally, we argue that as a corollary of Theorem 1, there is no fully black-box construction of a PRF from a PRG using a query-bounded reduction and a constant number of non-adaptive calls, regardless of the input length of the PRF. Indeed, for in = O(log n) PRFs can be constructed unconditionally by simply letting the key be the truth table of the function (in particular, there is no reduction). On the other hand, for in = ω(log n), Theorem 1 states that there is no fully black-box construction with a constant number of calls. Note that this resolves the question of the single call case for query-bounded reductions. A lower-bound for black-box constructions with long outputs. We show an additional lower bound for PRFs with long outputs. Unlike in Theorem 1, here the result holds for adaptive constructions and does not require assuming the reduction to be query-bounded. Theorem 2 (Informal, lower bounds for long output constructions). There is no fully black-box construction of a PRF with output length out from a out PRG with stretch r using at most max(r,ω(log n)) calls. Stated differently, if r = O(log n), then Theorem 2 states that there is no black-box construction using o(out/ log n) calls to the PRG. On the other hand, if r = ω(log n), then there is no black-box construction using o(out/r) calls. Additionally, similarly to Theorem 1, the proof of Theorem 2 also applies to weak PRFs. Let us compare Theorem 2 to the GGM construction (note that in the GGM construction, the output of the PRF is of length n, making it natural to compare to). The GGM construction (combined with Levin’s trick) is an n-bit output PRF from an n-bit stretch PRG using ω(log n) calls to the PRG. The PRG can be constructed from a 1-bit stretch PRG using O(n/ log n) calls using the GoldreichLevin hardcore function theorem [9]. Thus, the overall number of calls the PRF construction makes to a 1-bit stretch PRG is ω(n). By Theorem 2, the number 3

of calls must be at least n/ω(log n). This means that the GGM construction is optimal up to a factor of ω(log n). The formal statement of Theorem 2 appears in Section 5. 1.2

Related Works

Separation of cryptographic primitives is a fundamental question in cryptography that qualitatively measures the relative hardness of different cryptographic primitives. The seminal work of Impagliazzo and Rudich [12] provided the first separations ruling out constructions of key exchange from one-way functions. The class of constructions ruled out in this work is referred to as a fully blackbox construction (see [18] for a taxonomy on reductions) where the construction uses the underlying primitive as a black-box and the reduction is black-box. Within the framework of black-box separations, the meta-reduction paradigm introduced in the work of Boneh and Venkatesan [5], considers designing a (possibly inefficient) attacker A that when invoked with the reduction breaks the challenge in the underlying security reduction, then emulating A in a manner that is efficient and does not affect the interaction of the reduction and the challenger (see also [6, 11, 7, 16, 17]). We follow the meta-reduction paradigm in this work (see [1] and references therein). Miles and Viola [14, 15] were the first to consider lower bounds on blackbox constructions of PRFs from PRGs.5 They ruled out single-call constructions where the output is one of the PRG’s output bits. More recently, Beimel et al. [2] both generalized the result of [14, 15], and proved a lower bound on the number of calls in tree constructions, which naturally generalize the GGM construction. Additionally, they showed a lower bound on the key length required for black-box constructions. A related question is that of constructing PRFs from non-adaptive PRFs (naPRF), where security is only guaranteed to hold against adversaries who make non-adaptive queries. Berman and Haitner [4] showed a non-uniform construction of a PRF from a naPRF that uses a single call. They further showed a uniform construction using ω(1) calls. Related to our results, Soni and Tessaro [19] showed that certain fully black-box non-adaptive constructions of PRFs from naPRFs are impossible. 1.3

Organization

We give an overview of our techniques in Section 2. The preliminaries are given in Section 3. Then, in Section 4 we prove our main result, showing a lower bound for constructions with non-adaptive calls. Finally, in Section 5, we prove our lower bound for PRFs with long outputs.

5 The paper considers the question of extending the stretch of a PRG; however, they noted in [15] that their result applies to constructing PRFs from PRGs as well.

4

2

Our Techniques

We now present our techniques. We start with showing the impossibility for non-adaptive black-box constructions. 2.1

Lower Bounds for Fully Black-Box Constructions

As a warm-up, we will rule out PRF constructions that make a single call to a PRG and then generalize this argument for multiple non-adaptive calls. 2.1.1 Warm-Up: The Single Call Case Since we assume the construction makes one call to the PRG, we may write it as fkG (x) = P (x, k, G(S(x, k))) , for efficiently computable functions S and P . In the following, let λ denote the length of the keys, and let r denote the stretch of G. Standard black-box separation like the approaches in [14, 2] construct an oracle O relative to which a PRG G exists, and construct an oracle-aided algorithm AO that breaks the security of F using a polynomial number of calls to O. We argue that it may be impossible to use such an approach to rule out black-box constructions of PRF from a PRG. Consider the following PRF construction from an r-bit stretch PRG G: G fh,k (x) = ⟨G(h(x)), k⟩

where the key is a pair (h, k), where h is sampled from a pairwise independent hash function family, k ← {0, 1}n+r , and ⟨·, ·⟩ is the inner product computed modulo 2. If G is instantiated via a random oracle, then, for any polynomial set of inputs x1 , . . . , xm , the set {h(x1 ), . . . , h(xm )} will all be distinct (except with negligible probability). This would imply that the entropy of each G(xi ) is large enough (given the other outputs of f ) and the inner product can extract a random bit, such that the m bits are statistically close to a uniform sample from {0, 1}m . In fact, this argument works even if G is only “mildly” random, e.g., G applies a random function only to the first ω(log n) bits. Since the proof of security of the PRF is information-theoretic and does not depend on the reduction, it may be impossible to rule out such constructions using random oracles and an adversary AO that calls O a polynomial number of times. Since the work of Gennaro and Trevisan [8], most black-box separations from a random oracle have pursued this approach. We circumvent this challenge by relying on the meta-reduction paradigm. We first define an “ideal” adversary that breaks the PRF using an exponential number of queries to the PRG. We then construct an inefficient “real” adversary that can simulate the ideal adversary when given the queries made by the reduction to the PRG. The idea here is that such an adversary can be simulated together with the reduction. In other words, we construct an algorithm that breaks the security of the PRG by emulating the reduction with real adversary that together make only polynomial queries to the underlying PRG. 5

A naive attempt. Let us start with a naive construction for the real and ideal adversaries that does not work. Define the ideal adversary AG,f ideal to query G on all inputs, and query the PRF/random function f on m distinct inputs x1 , . . . , xm . The adversary outputs 1, indicating PRF, if and only if it can find a key that is consistent with all the responses. Clearly, if f is sampled from the PRF family, Aideal will always output 1. When f is sampled from the random function family, we can show that it will output 1 with negligible probability, assuming m is sufficiently large via an entropy argument. Since the key length is λ, if m = λ+n, then except with probability 2−n , there will not be a consistent key. Now, consider the following “real adversary” that aims to emulate the ideal adversary. This adversary queries its oracle (whose answers are given by reduction) on m inputs just like the ideal adversary, but along with the responses from the reduction, it also receives all queries made by the reduction to the PRG. The idea is that in order for the responses to be consistent with the PRF family, the reduction must have queried the PRG on all the points needed to emulate the PRF for some key k. Thus, using the query-answers provided to the real adversary, we let it (in exponential time) find the key k without making any additional queries to the PRG itself. If it finds such a key, the adversary outputs 1 indicating PRF and outputs 0 otherwise. This adversary seemingly emulates the ideal adversary. However, this is not the case. The reduction does not have to make all the queries to the PRG consistent with a particular key to compute the answers. In fact, in the GGM reduction, the adversary implants the challenge string as the output of a PRG call. This means that the above strategy for the real adversary fails, because the reduction may have computed some of the outputs using some key and querying G, but guessed the other outputs (without querying G). Therefore, the real adversary cannot find a consistent key, while the ideal adversary may find one. Our first observation is that the reduction cannot guess too many of the outputs, while still being consistent with some key. Indeed, otherwise, the probability that it is consistent with some key becomes negligibly small. Thus, we can revise the strategy of the two adversaries to only look for a key that is consistent with, say, 0.8 fraction6 of the inputs. Indeed, when using 0.8 as the threshold, if the ideal adversary interacts with a random function f , then for every key, on expectation, only 1/2 of the answers are consistent with the inputs. By a simple concentration bound, it will not find a key except with negligible probability. Unfortunately, there is the issue of the reduction guessing too few of the outputs. Specifically, in the case where the reduction computed correctly only 0.7 fraction of the inputs, we do not know how to show that the ideal adversary will not find a different key that is consistent with 0.8 fraction of the inputs. We introduce two ideas to solve this. Towards describing our ideas, we first introduce two score functions (one for each adversary). For the ideal adversary, the score function with respect to some key is simply the number of consistent input-output pairs. The real adversary estimates the score function of the ideal 6 The choice of 0.8 is arbitrary; any constant larger than 1/2 and smaller than 1 works.

6

adversary by considering the probability that it will be consistent with the answers (instead of a binary value). Specifically, for every key k the real score is computed as follows: for every x that is one of the m inputs (and S(x, k) has not been queried by the reduction), compute the probability over a random G′ ′ that is consistent with the reduction queries, that fkG (x) equals the value given to it by the reduction. This probability can be computed exactly by the real adversary. The final score of the real adversary for k is the sum of these probabilities over all inputs. By linearity of expectation, it is equal to the expected score of the ideal adversary (for the same key). The final score of each of the real and ideal adversaries is its maximal score over all keys, and the answer (PRF/random function) is defined by comparing this score to some threshold. However, choosing a fixed threshold could fail in case it falls between the real and ideal scores (which could happen even if the scores are very close). Therefore, the second idea is to choose a random threshold between 0.8 and 1. This helps to smoothen the difference and as long as the real and ideal scores are close enough. However, there are still two issues with the above argument. 1. Although for every k, the score of the real adversary equals the expected score of the ideal adversary, the final outputs of the PRF on the m inputs might be dependent. Hence, we cannot claim that the scores are close with high probability. For a key k, such dependencies occur if for two different inputs xi and xj , S(xi , k) = S(xj , k). 2. The second issue relates to the challenge y ∗ held by the reduction. Recall that y ∗ is either uniform over {0, 1}n+r , or equals to G(s), where s ← {0, 1}n . In the latter case, if the reduction implant y ∗ instead of G(S(xi , k)) for some i, then this increases the ideal score by 1, but increases the real score only by a negligible amount. Otherwise, the challenge affects the scores the same, which may provide the reduction a way to distinguish between the two adversaries. Fixing the issues. To solve the problems, we aim to break the dependencies between the outputs of the PRF. This solves the first issue as it allows us to use Chernoff’s inequality to argue that the two scores are close with high probability. It also solves the second one since if the outputs are independent, the challenge can only affect at most one output (keeping the scores close). Towards breaking the dependencies, we observe that for every key k, either there is a PRG query that appears for many inputs, or we can find a large set of inputs with distinct PRG seeds. Claim 3 (Informal). For a positive integer parameter p (to be chosen), one of the following must hold for every key k. 1. There exists a seed that appears at least p times in {S(xi , k) : i ∈ [m]}, or 2. There is a set I ⊆ [m] of at least m/p inputs with distinct PRG seeds. Proof. Consider the graph H = ([m], E), where i, j is an edge if and only if S(xi , k) = S(xj , k). If Item 1 does not hold, then the maximum degree in H 7

is at most p − 1. By greedily selecting the vertices, we conclude there is an independent set of size at least m/p. By definition, the PRG seeds associated with an independent set are distinct. □ Now, if for a key k the second item holds, then our previous argument works when restricting to I: Since we instantiate the PRG with a random oracle, this implies that the corresponding outputs are independent random variables (over the PRG random oracle). This independence allows us to use a concentration bound to argue that if m/p is sufficiently large, then the real adversary can predict the output of the ideal adversary with good accuracy. As for the other keys, we argue that there is only a negligible fraction of them. Indeed, if for too many keys there is a seed s that appears at least p times then, intuitively, for a random key the entropy in the output for those p inputs is bounded by λ + n + r. Thus, for a sufficiently large p, the PRF can be distinguished from random. As a result, we may allow both the real and ideal adversaries to ignore such keys. With this, for any polynomial u, we can choose m so that for every call made by the reduction to the adversary, the statistical gap between the real and ideal adversary’s outputs is 1/u-close. However, recall that the reduction can call the adversary polynomially many times, say v. If we want the argue that the statistical gap for all the combined outputs are close we need v/u to be small. In other words u should be chosen after v. Since m depends on u, for our impossibility to hold, we need to assume that the number of calls made by the reduction v is independent of m. We believe this is a reasonable restriction and discuss this further in Section 2.1.3. 2.1.2 The General Case. We now describe our ideas to generalize the single call case to c non-adaptive calls, where c = o(n/ log n) and c = o(in/ log in). Recall that to define the two adversaries, we define two score functions (one for each adversary) that aim to compute for how many inputs the reduction returned the correct output (with respect to some key). The two score functions are defined with respect to each key, via a procedure that depends only on the construction of the PRF (in particular, it is independent of the output of the PRG). This is important, since the score function does not require the real adversary to make any PRG queries. As in the single call case, the goal of the functions is to find a large set of inputs that make disjoint PRG queries. At a high level, this is done by letting the score functions try to break the dependence between some PRF outputs by fixing PRG outputs on queries that are made by many PRF inputs. Specifically, the procedure works in iterations as we next describe. In each iteration, the adversaries looks for a seed s that appears for sufficiently many inputs (i.e., for many of the xi ’s, at least one of the seeds needed to compute fkG (xi ) is s). For such seeds, the PRG will not contribute much entropy to the output of the PRF (taken over all inputs that query s). When we define the scores, we replace G(s) with a fixed value that maximizes the score and is independent of G. In such a case, the construction is left with one less call to the PRG. This process continues until either no s appear many times, or until 8

the process finds c such seeds. In the former case, we can apply (a generalization of) Claim 3 to argue that there is a large set of inputs with a mutually disjoint set of seeds, while in the latter case, we will later replace all calls to the PRG with fixed values. In more detail, for every key k, the final output of the procedure is a list of ℓ(k) ≤ c seeds s1 , . . . , sℓ(k) and a list of nested sets of inputs I1 ⊇ . . . ⊇ Iℓ(k) . We require that each st appears for sufficiently many inputs in It . The score calculation is then done by replacing each G(st ) with a fixed value. If ℓ(k) = c, then the scores are fixed and independent of G. Otherwise, there is a set I ⊆ Iℓ(k) of inputs with mutually disjoint seeds. The score calculation is then done the same as in the single call case. For the argument to work, we need to ensure that at every step, the set of inputs It that are being considered is sufficiently large. Specifically, if the |It | procedure stops early, then Claim 3 implies the existence of a set of (c−t)|I t+1 | inputs with mutually disjoint queries. For the concentration bound to work, this ratio needs to be sufficiently large (Specifically, it needs to be larger than some fixed polynomial that depends on the key length, the PRG stretch, and the reduction). If the procedure replaces every G(st ), we need |Iℓ(k) | to be sufficiently large as well to argue that the PRF can be distinguished from a random function. This implies that the number of inputs required is m = (poly(n))c · c!. For the adversaries to be well-defined, this value must be upper bounded by 2in , which holds for all sufficiently large n’s by our assumption that c = o(in/ log in). Additionally, the total number of queries that R makes to the PRG is d · mβ , for some constant β ∈ N and where d is the number of calls R makes to the distinguishing adversary. Recall that c = o(n/ log n), hence d · mβ ≤ 2n/4 for all sufficiently large n’s. Since we instantiate the PRG with a random function, 2n/4 queries are insufficient to break its security (see Lemma 1 for the formal statement), resulting in a contradiction. 2.1.3 Subtleties With Oracle Access to PRF Distinguishers. The standard definition of a fully black-box reduction from PRF to PRG is as follows. Given access to an oracle-adversary A(·) that is able to distinguish the PRF from a random function, the reduction, a ppt oracle-aided algorithm R is able to distinguish the output of G(s), where s ← {0, 1}n , from a string uniformly sampled from {0, 1}|G(s)| . Since we fixed R, its run-time is some fixed polynomial, say T (n). The adversary Af is allowed to query f a polynomial m number of inputs. When activated by the reduction, A expects m(n) answers. These should be provided by R; however, m is chosen by A, which is fixed after R, hence m cannot depend on T . In particular, if m(n) > T (n), then R has no time to answer A’s queries. For the model to make sense, we have to treat the m inputs chosen by A as part of the reduction’s input. However, now the reduction depends on A. For example, after receiving the m inputs from A, the reduction can decide to call it m more times. If we now replace A with another adversary that sends m + 1 inputs, and apply A on the first m answers (i.e., it ignores the last input 9

and output), then R calls it more times than with A, thus the entire procedure changed, even though the adversary does the same. Such reductions are arguably not “black-box”. Recall that in our proof, we had to assume that the reduction cannot depend on the number of inputs given by the distinguishing oracle. This means that our proof does not hold for the standard notion of fully black-box constructions. Instead, we consider query-bounded reductions. These are reductions whose number of calls to the adversary is bounded by some polynomial d(n) for all adversaries whose distinguishing advantage is sufficiently large. Specifically, for our proof, we assume that there exists a polynomial d(n) such that for any adversary A whose distinguishing advantage is at least α(n) = 1 − e−n , the reduction calls A at most d(n) times. Note that any reduction whose number of calls to A decreases as a function of the distinguishing advantage of A is also query-bounded (perhaps with a different α(n)). We argue that the class of query-bounded reductions is both natural and well-motivated. Indeed, all reductions previously considered in the literature, to the best of our knowledge, satisfy this property and thus fall within the class of query-bounded reductions. This includes, for example, the GGM construction [10], Goldreich and Levin [9] hardcore predicate construction, and Waters [20] construction of signature schemes. We refer the reader to Definition 4 for a formal definition of query-bounded reductions.

2.2

Lower Bounds for PRFs With Long Outputs

We now prove Theorem 2. To simplify this introduction, we will prove a simpler result that considers constructions with a single call to the PRG (see Section 5 for the proof of the general result). Although it is not as general, the proof highlights the key ideas of our techniques. Specifically, we show that if out − r = ω(log n), then there is no black-box construction of a PRF with output length out from a PRG with stretch r using a single call to the PRG. Let in = in(n) and assume that F = {fkG : {0, 1}in → {0, 1}out }n∈N,k∈{0,1}λ is a PRF construction that calls G : {0, 1}n → {0, 1}n+r once. The main idea of the proof is to consider the entropy of sufficiently many applications of the function. That is, given access to a function f (that is either truly random or sampled from F ), we consider the total entropy of m applications of f on different inputs, where m = m(n) is a sufficiently large polynomial. Observe that for a random function the entropy is maximized, i.e., it is out · m. However, we show how to construct a PRG G such that the entropy of m applications of fkG is noticeably far from out · m. Intuitively, this is achieved by considering a PRG that is only applied to the first out − r − 1 = ω(log n) bits of the input. This ensures that the entropy in the output comes from the key k and the out − 1 (pseudo)random bits obtained from the stretch of G. Thus, the entropy will be at most λ+m·(out−1). Taking m = λ + n results in a gap of n from out · m, which we show is sufficient. We note that the above argument works for all fully black-box reductions, and not just query-bounded ones, as was needed in Theorem 1. 10

3

Preliminaries

3.1

Notations

For n, m ∈ N we let [n] = {1, 2 . . . n} and let [n] m = {S ⊆ [n] : |S| = m}. All logarithms are taken in base 2. For a set S, we write s ← S to indicate that s is selected uniformly at random from S. Given a random variable (or a distribution) X, we write x ← X to indicate that x is selected according to X. ppt stands for probabilistic polynomial time. A function µ : N → [0, 1] is called negligible, if for every positive polynomial p(·) and all sufficiently large n, µ(n) < 1/p(n). For n, m ∈ N, we let Fn,m = {f : {0, 1}n → {0, 1}m } denote the set of all functions from {0, 1}n to {0, 1}m , and let Fn = Fn,1 . Theorem 4 (Hoeffding’s inequality). Let X1 , . . . , Xn ∈ {0, 1} denote independent random variables such that Pr [Xi = 1] = pi for all i ∈ [n] for some Pn pi ∈ (0, 1). Let p = i=1 pi . Then for every t > 0, " n # X 2 Pr Xi ≥ pn + t ≤ e−2t /n i=1

and Pr

" n X

# 2

Xi ≤ pn − t ≤ e−2t /n .

i=1

3.2

Pseudorandom Generators

Definition 1 (Pseudorandom generator (PRG)). An efficiently computable function G is an r(n)-bit stretch PRG if for every n ∈ N and s ∈ {0, 1}∗ , |G(s)| = |s| + r(|s|) and for every ppt algorithm A, there exists a negligible function µ such that Prs←{0,1}n [A(1n , G(s)) = 1] − Pry←{0,1}n+r(n) [A(1n , y) = 1] ≤ µ(n). The following lemma states that a random function is a PRG with overwhelming probability. Lemma 1. The following holds for every r : N → N, and all sufficiently large n ∈ N. Let G : {0, 1}n → {0, 1}n+r(n) be a function chosen uniformly at random and C be a 2n/4 -call oracle aided (possibly inefficient) algorithm. Then with probability at least 1 − 2−n/2 ,     Prs←{0,1}n C G (G(s)) = 1 − Pry←{0,1}n+r(n) C G (y) = 1 ≤ 2−n/4 . Proof. By Markov’s inequality, it suffices to show that      EG←Fn,n+r(n) Prs←{0,1}n C G (G(s)) = 1 − Pry←{0,1}n+r(n) C G (y) = 1 ≤ 2−3n/4 . This is done by lazy sampling [3]. Assume without loss of generality that C makes only distinct queries to the oracle. Let P0 : {0, 1}n → {0, 1}n+r(n) be the procedure defined as follows: 11

1. Sample s ← {0, 1}n and y ← {0, 1}n+r(n) , independently. 2. On query x ∈ {0, 1}n , sample y ∗ ← {0, 1}n+r(n) . 3. If s = x, then set bad = true. Set y = y ∗ . 4. Return y. Additionally, let P1 : {0, 1}n → {0, 1}n+r(n) be the procedure defined as follows: 1. Sample s ← {0, 1}n and y ← {0, 1}n+r(n) , independently. 2. On query x ∈ {0, 1}n , sample y ∗ ← {0, 1}n+r(n) . 3. If s = x, then set bad = true. 4. Return y. First, note that      EG←Fn,n+r(n) Prs←{0,1}n C G (G(s)) = 1 = Pry∗ ←{0,1}n+r(n) C P0 (y ∗ ) = 1 and that      EG←Fn,n+r(n) Pry←{0,1}n+r(n) C G (y) = 1 = Pry←{0,1}n+r(n) C P1 (y) = 1 . Therefore,     Prs←{0,1}n C G (G(s)) = 1 − Pry←{0,1}n+r(n) C G (y) = 1     ≤ Pry∗ ←{0,1}n+r(n) C P0 (y ∗ ) = 1 − Pry←{0,1}n+r(n) C P1 (y) = 1

EG←Fn,n+r(n)



Now, observe that the procedures P0 and P1 are identical-until-bad, namely, they return identically distributed answers until bad occurs. Since C can make 2n/4 queries, bad occurs with probability at most 2n/4−n = 2−3n/4 . Therefore,     Pry∗ ←{0,1}n+r(n) C P0 (y ∗ ) = 1 − Pry←{0,1}n+r(n) C P1 (y) = 1 ≤ 2−3n/4 . □ 3.3

Black-Box Constructions of Pseudorandom Functions

We next define black-box constructions of a pseudorandom function (PRF) from PRGs. Definition 2 (Fully black-box PRF constructions). A fully black-box construction of a PRF from an r(n)-bit stretch PRG is a pair (F, R) where n o (·) F = fk : {0, 1}in(n) → {0, 1}out(n) λ(n) n∈N,k∈{0,1}

is an efficiently computable oracle-aided function family, and R(·),(·) is a ppt oracle-aided algorithm such that the following holds. There exists a polynomial q : N → N such that for every G = {Gn : {0, 1}n → {0, 1}n+r(n) }n∈N and every oracle-aided algorithm A(·) for which there exists a constant c ∈ N such that h G i   1 Prk←{0,1}λ(n) Afk (1n ) = 1 − Prf ←Fin(n),out(n) Af (1n ) = 1 ≥ c n 12

for infinitely many n’s,     Prs←{0,1}n RA,G (1n , G(s)) = 1 − Pry←{0,1}n+r(n) RA,G (1n , y) = 1 ≥

1 q(nc )

for infinitely many n’s. (F, R) is fully black-box construction of a weak PRF, if the above holds for all algorithms A that query i.i.d. uniform queries to f . We next define the query complexity of a black-box construction. Definition 3 (c-call adaptive and non-adaptive constructions). Let in(n), out(n), r(n), and λ(n) be polynomials, and let n o (·) F = fk : {0, 1}in(n) → {0, 1}out(n) λ(n) n∈N,k∈{0,1}

be a black-box PRF construction from an r(n)-bit stretch PRG. For a function c : N → N, we say that F is a c(·)-call construction if for every i ∈ [c(n)] there exist Si : {0, 1}in(n) × {0, 1}λ(n) × ({0, 1}n+r(n) )i−1 → {0, 1}n and P : {0, 1}in(n) × {0, 1}λ(n) × ({0, 1}n+r(n) )c(n) → {0, 1}out(n) such that fkG (x) = P (x, k, G (s1 ) , . . . , G(sc )) for all G : {0, 1}n → {0, 1}n+r(n) , where si = Si (x, k, G (s1 ) , . . . , G(si−1 )) for all i ∈ [c(n)]. We say that the construction is non-adaptive if every Si depends only on x and k. In our proof, we consider a restricted notion of black-box reductions that have access to a distinguisher with oracle access to a function. Roughly, this class captures reductions where the number of times it can query the adversary is bounded by a polynomial for all sufficiently good adversaries. Definition 4 (Query-bounded reductions). Let (F, R) be a fully black-box construction of a PRF from an r(n)-bit stretch PRG, where n o (·) F = fk : {0, 1}in(n) → {0, 1}out(n) , λ(n) n∈N,k∈{0,1}

let ε : N → [0, 1], and let d : N → N. We say that RG,A is (d, ε)-query-bounded if for every oracle-aided algorithm A· such that h G i   Prk←{0,1}λ(n) Afk (1n ) = 1 − Prf ←Fin(n),out(n) Af (1n ) = 1 ≥ 1 − ε(n) for infinitely many n’s, RG,A calls A at most d(n) times. Note that any reduction that is (d, ε)-query-bounded is also (d, ε′ )-querybounded for any ε′ such that ε′ (n) ≥ ε(n). Therefore, for our impossibility result, proving it for a larger ε yields a stronger result. 13

4

Lower Bounds for Fully Black-Box Constructions of PRFs From PRGs

In this section, we prove our main result. We show that there is no fully black-box construction of PRF with input length in from a PRG with c calls to the PRG and using a query-bounded reduction, where c = o(n/ log n) and c = o(in/ log in). We are now ready to state and prove our main result. Theorem 5. Fix polynomials r : N → N and in : N → N such that in(n) = ω(log n). Then for every c : N → N such that c(n) = o (n/ log n) and c(n) = o (in/ log in), and for every polynomial d : N → N, there is no c(n)-call nonadaptive fully black-box construction of a weak PRF with input length in(n) and a single-bit output from an r(n)-bit stretch PRG, with a (d, e−n )-query-bounded reduction. Proof. We first give an overview of the proof. Our proof has 4 major steps. Step 1: We fix m inputs x1 , . . . , xm for a sufficiently large m. Then, for every key k, we identify a large subset of the inputs Ik based on repetitions in the seeds generated by the key and the inputs in Ik . Specifically, we show that either there are c seeds that are common to all inputs in Ik , or there t < c common seeds and the rest of the seeds are mutually disjoint. Importantly, this step is independent of the PRG, i.e., the set Ik is the same for every PRG. We formalize the properties of the set Ik and show its existence in Lemma 2. Step 2: Next, we define an “ideal adversary” Af,G ideal that breaks the PRF by inverting the PRG G. This adversary is not optimal. Instead of outputting ‘PRF’ when all input-output pairs (given by the oracle f ) are consistent with respect to some key k, we define a score function based on the number of consistent input-output pairs in the set Ik , and let Af,G ideal output ‘PRF’ if and only if the score is larger then a random threshold sampled uniformly at random. We prove, nonetheless, that this ideal adversary breaks the PRF. This is formalized in Claim 8. Step 3: We then define a “real adversary” whose goal is to simulate the ideal adversary without inverting the PRG. It is given the query-answer pairs generated by the reduction’s interaction with the PRG. Roughly, the difference between the real adversary and the ideal adversary is in the definition of the score functions they compute. We show that the real adversary behaves close to the ideal adversary. We formally prove this in Lemma 3. Step 4: Finally, we combine the previous steps to argue that the reduction can successfully break the PRG using the real adversary. Since the real adversary does not query the PRG, we conclude the existence of an algorithm for breaking the PRG using a sub-exponential number of queries. Thus, instantiating the PRG with a random function will contradict Lemma 1, concluding the proof. Assume towards contradiction that the claim is false. That is, there exists polynomials in = in(n), λ = λ(n), and r = r(n), there exists c = c(n) such that 14

c = w(n)nlog n and c = w(n)inlog in for some w(n) = ω(1), there exists a polynomial d = d(n), and there exists a fully black-box construction (F, R) such that R is (d, e−n )-query-bounded. We write n o (·) F = fk : {0, 1}in → {0, 1} n∈N,k∈{0,1}λ

(·)

where fk is given by fkG (x) = P (x, k, G(S1 (x, k)), G(S2 (x, k)), . . . , G(Sc (x, k))) , for efficiently computable functions S1 , S2 , . . . , Sc : {0, 1}in × {0, 1}λ → {0, 1}n and P : {0, 1}in × {0, 1}λ × ({0, 1}n+r )c → {0, 1}. The proof follows the meta-reduction paradigm. We first define an “ideal” adversary that breaks the PRF using an exponential number of queries to the PRG. We then construct an inefficient “real” adversary with no access to the PRG that is able to simulate the ideal adversary, when provided with the collection of query–answer pairs generated by the reduction’s interaction with the PRG. We then conclude that there exists an algorithm that breaks the security of the PRG using fewer than 2n/4 queries, by running the reduction and using the real adversary. For the argument to follow through, we have to ensure that the reduction cannot distinguish between the ideal and real adversaries. We are unable to show that the statistical distance between the responses of the adversaries is negligible. Instead, we show that the distance is 1/ poly(n), for some polynomial poly(n) that depends on both the number of calls d made by the reduction to the adversary, and the number of queries m(n) made by the adversary (to its oracle function). Thus, poly(n) must be sufficiently large, implying that m(n) must be sufficiently large compared to d. Consequently, d must be fixed prior to m(n); otherwise, the argument would suffer from a circular dependence among d and m(n). This requirement is exactly the reason we assume the reduction to be query-bounded, as it ensures that d is determined independently of the adversary. We note that if one could construct real and ideal adversaries whose response distributions have negligible statistical distance, our assumption would no longer be necessary. We first introduce some notation. For every t ∈ {0, 1, . . . , c}, let mt = mt (n) be a parameter (not necessarily a polynomial) to be defined by the analysis below. Further, let m = m0 and fix m distinct inputs x1 , . . . , xm ∈ {0, 1}in .7 Step 1: Identifying frequent seeds. In the first step of the proof, our goal is to identify for every key k ∈ {0, 1}λ the set Ik of inputs with many common seeds. Towards defining Ik , we use the following claim, which states that for every set of t < c seeds S, if every PRG seed outside of S appears a few times among a subset I0 ⊆ [m] of the inputs, then for a large fraction of these inputs, the only common seeds belong to S. 7 Note that if we obtain a contradiction for all distinct inputs, then the same holds for random inputs (up to adding the birthday bound).

15

Claim 6. Fix a number p ∈ [m] and a key k ∈ {0, 1}λ . Further fix a set of inputs I0 ⊆ [m] and a set of seeds S ⊆ {0, 1}n of size |S| = t ∈ {0, 1, . . . , c − 1} , such that for every s ∈ S and i ∈ I0 there exists j ∈ [c] such that s = Sj (xi , k). Assume that there is no s ∈ {0, 1}n \ S and I ⊆ I0 of size p such that \ s∈ {Sj (xi , k) : j ∈ [c]} . i∈I

Then there exists a set I ′ ⊆ I0 of size |I ′ | ≥

|I0 | |I0 | ≥ , (c − t)(p − 1) + 1 (c − t)p

such that the sets of PRG queries generated by them (outside of S) are mutually disjoint, i.e., Sj (xi , k) ∈ / {Sj ′ (xi′ , k) : j ′ ∈ [c], i′ ∈ I ′ \ {i}} \ S, for every i ∈ I ′ and j ∈ [c]. Proof. Consider the graph H = (I0 , E) where {i, i′ } ∈ E for i ̸= i′ if and only if xi and xi′ share a common PRG query outside of S, i.e., ({Sj (xi , k) : j ∈ [c]} \ S) ∩ ({Sj (xi′ , k) : j ∈ [c]} \ S) ̸= ∅. Observe that the set I ′ we aim to show exists, corresponds to an independent set in H. By assumption, every PRG query s ∈ {0, 1}n \ S appears at most p − 1 among the set of all seeds in {Sj (xi , k) : i ∈ I0 , j ∈ [c]}. Thus, for every vertex i ∈ I0 , every j ∈ [c] such that Sj (xi , k) ∈ / S contributes 1 to the degree of i. Since by assumption there are exactly t indexes j ∈ [c] such that Sj (xi , k) ∈ S, the degree of each vertex in H is at most (c−t)(p−1). Therefore, by greedily picking vertices for an independent set and removing their neighbors, we conclude that there exists an independent set of vertices of size at least |I0 |/((c − t)(p − 1) + 1). □ Recall that to construct the two adversaries, we define two score functions (one for each adversary) that aim to compute for how many inputs the reduction returned the correct output (with respect to some key). The two score functions are defined with respect to each key, via a procedure that depends only on the construction of the PRF (in particular, it is independent of the output of the PRG). This is important, since the score function does not require the real adversary to make any PRG queries. At a high level, the procedure works in iterations, where in each iteration it looks for a seed s that appears for sufficiently many inputs (i.e., for many of the xi ’s, at least one of the seeds needed to compute fkG (xi ) is s). The process continues until either no s appear many times, or until the process finds c such seeds. In the former case, we can apply Claim 6 to argue there is a large set of inputs with mutually disjoint set of seeds, while in the latter case, we will later replace all calls to the PRG with fixed values. The following lemma summarizes this. 16

Lemma 2. For every key k ∈ {0, 1}λ , there exists a number ℓ(k) ∈ {0, 1, . . . , c}, there exist ℓ(k) distinct seeds sk = (sk,1 , . . . , sk,ℓ(k) ) ∈ ({0, 1}n )ℓ(k) , and there exists a set Ik ⊆ [m] such that the following holds. T 1. If ℓ(k) = c, then |Ik | = mc and sk,t ∈ i∈Ik {Sj (xi , k) : j ∈ [c]} for every t ∈ [c]. mℓ(k) , 2. Otherwise, if ℓ(k) < c, then |Ik | = (c−ℓ(k)+1)m ℓ(k)+1 Sj (xi , k) ∈ / {Sj ′ (xi′ , k) : j ′ ∈ [c], i′ ∈ Ik \ {i}} , for every i ∈ Ik and j ∈ [c], and T there exists a set I ⊆ [m] of size |I| = mℓ(k) such that Ik ⊆ I and sk,t ∈ i∈I {Sj (xi , k) : j ∈ [c]} for every t ∈ [ℓ(k)]. Proof. The proof follows from greedily looking for the next seed sk,t and the (sufficiently large) set of inputs generating it, until we found c such seeds, or it does not exist and we can apply Claim 6. Formally, the lemma follows from considering the following procedure: 1. Let Ik,0 = [m] and t = 1. 2. While t ≤ c do the following: – If there exists a seed s ∈ {0,T 1}n \ {sk,1 , . . . , sk,t−1 } and I ⊆ Ik,t−1 of size |I| = mt such that s ∈ i∈I {Sj (xi , k) : j ∈ [c]}, then let sk,t and Ik,t denote the lexicographically smallest such seed s and set I, and increment t by 1. – Otherwise, by Claim 6, there exists a set of inputs I ⊆ Ik,t−1 of size |I| =

mt−1 |Ik,t−1 | = (c − t) · mt (c − t) · mt

such that Sj (xi , k) ∈ / {Sj ′ (xi′ , k) : j ′ ∈ [c], i′ ∈ I \ {i}} , for every i ∈ I and j ∈ [c]. Let ℓ(k) = t − 1, and let Ik denote lexicographically smallest such set I, and halt. 3. Let ℓ(k) = c and Ik = Ik,c . □ It will be convenient to consider the value ν = mink |Ik |. Step 2: Defining the ideal adversary. We next define the first score function, which we call the ideal score function. It depends on the entire PRG oracle and will only be used by the ideal adversary. Given a key and a sequence of possible outputs z ∈ ({0, 1})m ,8 the score is defined by using Lemma 2 to find the seeds that appear many times. It then replaces the output of G on those seeds with fixed values, and returns the number of inputs in Ik that are consistent with z. 8

The score also implicitly depends on the inputs x1 , . . . , xm we fixed earlier.

17

In what follows, for every pair of sequences s = (s1 , . . . , st ) ∈ ({0, 1}n )t and y = (y1 , . . . , yt ) ∈ ({0, 1}n+r )t , define n o (·) Fs,y = fk,s,y : {0, 1}in → {0, 1} , n∈N,k∈{0,1}λ

(·)

(·)

where fk,s,y is the same as fk , except that for oracle queries in s, the oracle answer for the seed si is replaced with yi , for every i ∈ [t]. Definition 5 (Ideal score function). For every key k ∈ {0, 1}λ , every sequence of possible outputs z = (z1 , . . . , zm ), and every function G : {0, 1}n → {0, 1}n+r , define the ideal score of k to be 
G isG max i ∈ Ik : fk,s (xi ) = zi . k (z) = k ,y y∈({0,1}n+r )ℓ(k)

Observe that if ℓ(k) = c, then isG k (z) is independent of G. Next, we define the “ideal” adversary Af,G ideal for the PRF. This adversary queries the PRG on exponentially many inputs. We will then show that the reduction can simulate this adversary efficiently, resulting in an efficient distinguisher for the PRG. Roughly, Af,G ideal works as follows. First, it queries the oracle f on x1 , . . . , xm . The adversary outputs PRF if and only if there is a key whose ideal score is at least α · |Ik |, where α ∈ [0.8, 1] is sampled uniformly at random. .............................................................................. Algorithm 7 (Aideal ). Input: The security parameter 1n . Oracle access: A function f : {0, 1}in → {0, 1} and a PRG G : {0, 1}n → {0, 1}n+r . 1. Query G on every input in {0, 1}n . 2. Query f on x1 , . . . , xm . Let z = (z1 , . . . , zm ) denote the respective answers. 3. Sample α ∈ [0.8, 1] uniformly at random. 4. Output 1 if and only if there exists k ∈ {0, 1}λ such that isG k (z) ≥ α · |Ik |. ............................................................................. We first show that Af,G ideal indeed distinguishes the PRF from a random function. Claim 8. For all G : {0, 1}n → {0, 1}n+r , h G i h i fk ,G n n Prk←{0,1}λ Aideal (1 ) = 1 − Prf ←Fin Af,G (1 ) = 1 ≥ 1 − eλ+c(n+r)−ν/10 . ideal f G ,G

k Proof. We first show that Aideal (1n ) always outputs 1. Indeed, observe that 
G isG max i ∈ Ik : fk,s (xi ) = fkG (xi ) . k (z) = k ,y

y∈({0,1}n+r )ℓ(k)

Then taking yi = G(sk,i ) for every i ∈ [ℓ(k)] results in isG k (z) = |Ik |. 18

n To conclude the proof, we next show that for a random function f , Af,G ideal (1 ) λ outputs 1 with negligible probability. For every key k ∈ {0, 1} , every y ∈ ({0, 1}n+r )ℓ(k) , and every i ∈ Ik , define the random variable Xk,y,i to be the G indicator for the event fk,s (xi ) = f (xi ). Then k ,y

! isG k (z) =

max y∈({0,1}n+r )ℓ(k)

X

Xk,y,i

.

i∈Ik

Since f is a random function, these indicators are independent and have expectation 1/2. Therefore, for every k ∈ {0, 1}λ and every y ∈ ({0, 1}n+r )ℓ(k) , Hoeffding’s inequality (see Theorem 4) implies that " # X 2 Prf ←Fin Xk,y,i > 0.8 · |Ik | ≤ e−2·(0.8−0.5) ·|Ik | i∈Ik

≤ e−|Ik |/10 . Therefore, by the union bound, h i n Prf ←Fin Af,G ideal (1 ) = 1   ≤ Prf ←Fin ∃k ∈ {0, 1}λ : isG k (f (x1 ), . . . , f (xm )) ≥ 0.8 · |Ik | " # X = Prf ←Fin ∃k ∈ {0, 1}λ ∃y ∈ ({0, 1}n+r )ℓ(k) : Xk,y,i ≥ 0.8 · |Ik | i∈Ik

≤ 2λ+c(n+r) · e−ν/10 ≤ eλ+c(n+r)−ν/10 . □ mt−1 for some Recall that for every k ∈ {0, 1}λ , |Ik | = mc or |Ik | = (c−t+1)m t t ∈ [c]. Since ν ≥ |Ik | for every k ∈ λ, taking mc ≥ 10(λ + c(n + r) + n) and mt−1 ≥ (c − t + 1)mt · 10(λ + c(n + r) + n) for all t ∈ [c], results in the ideal adversary’s advantage begin at least 1 − e−n .

Step 3: Defining the real adversary. We now define the real score, which will be used by the real adversary. It is defined with respect to a set of query-answer pairs G instead of a PRG. The set G will later be instantiated with respect to the queries the reduction made to the PRG. Similarly to the ideal score, the computation of the real score also starts by replacing calls to G on seeds that appear many times with fixed inputs. The only difference is the end of the recursive process. There are two cases: either every call to G was replaced, or the inputs in Ik have mutually disjoint seeds. In the former case, the real score is identical to the ideal score. In the latter case, the score is defined as follows. Every input xi for which every remaining seed (i.e., for which the output of G was not fixed) belongs to the set G can be computed using G. Such inputs contribute 19

the same value as in the ideal score. For other inputs, the real score estimates its contribution to the ideal score by computing the probability over the PRG that the answer is correct. Since this is the case where all remaining seeds are mutually disjoint, the outputs corresponding to these inputs are independent random variables, and we can estimate their contribution to the score with high precision (see Lemma 3 below). In the following, for a set of PRG query-answer pairs G = {(sG1 , y1G ), . . . , (sGq , yqG )} ⊆ {0, 1}n × {0, 1}n+r we let sG denote the sequence of queries in G that do not appear in sk , and let yG denote the corresponding sequence of outputs. The reason not to include the queries in sk is that any query s made by the reduction is unknown to the ideal adversary, which maximizes its score over all possible values of G(s). Thus, the real adversary does the same, obtaining consistency between the two scores. Definition 6 (Real score function). For every key k ∈ {0, 1}λ , every sequence of possible outputs z = (z1 , . . . , zm ), and every set of PRG query-answer pairs G = {(sG1 , y1G ), . . . , (sGq , yqG )} ∈ {0, 1}n × {0, 1}n+r , define rsGk (z) as follows. – If ℓ(k) = c, then let rsGk (z) =

max

y∈({0,1}n+r )c

(|{i ∈ Ik : P (xi , k, y1′ , . . . , yc′ ) = zi }|) ,

where for every j ∈ [c], yj′ = yj ′ for the unique j ′ ∈ [c] such that Sj (xi , k) = sk,j ′ . – If ℓ(k) < c, then let ! h ′ i X G G rsk (z) = max PrG′ ←Fn,n+r fk,(sk ||sG ),(y||yG ) (xi ) = zi . y∈({0,1}n+r )ℓ(k)

i∈Ik

Similarly to the ideal score, if ℓ(k) = c then rsGk (z) is independent of G. In particular, in such a case, rsGk (z) = isG k (z). Since every ideal adversary we consider has advantage at least 1 − e−n , it follows that there exists a constant γ ∈ N such that for any G ∈ Fn,n+r ,     1 Prs←{0,1}n RAideal ,G (1n , G(s)) = 1 − Pry←{0,1}n+r RAideal ,G (1n , y) = 1 ≥ γ n (1) e(·) for infinitely many n’s. To obtain a contradiction, we construct an algorithm R that successfully breaks a randomly chosen PRG with noticeable probability, using at most 2n/4 queries to G and without having access to Aideal . Specifically, e such that we define R     eG ≤ 1 ≤ 3 , PrG←Fn,n+r Adv R (2) 3nγ 4 for infinitely many n’s, where   h i h i eG := Prs←{0,1}n R eG (1n , G(s)) = 1 − Pry←{0,1}n+r R eG (1n , y) = 1 , Adv R 20

eG . Note that Equation (2) contradicts Lemma 1. is the advantage of R e we first introduce an adversary Areal that, intuitively, effiBefore defining R, ciently emulates Aideal using the set of queries to G used so far by the reduction. Roughly, Areal works similarly to Aideal , but uses rs instead of is. We then show e run R, and replacing each call to Aideal with running Areal using by letting R the set of query-answer pairs of the PRG used so far, the answers of the two distinguishing oracles are close in statistical distance. .............................................................................. Algorithm 9 (Areal ). Input: The security parameter 1n , a sequence z ∈ {0, 1}m , and a set of queryanswer pairs G ⊆ {0, 1}n × {0, 1}n+r . 1. Sample α ∈ [0.8, 1] uniformly at random. 2. Output 1 if and only if there exists k ∈ {0, 1}λ such that rsGk (z) ≥ α · |Ik |. ............................................................................. e The algorithm simply runs R, replacing all We are now ready to define R. calls to Aideal by running Areal . .............................................................................. e Algorithm 10 (R). Input: The security parameter 1n and a challenge y ∗ ∈ {0, 1}n+r . Oracle access: A PRG G : {0, 1}n → {0, 1}n+r . 1. Simulate RA,G as follows. – Whenever R calls G, query G with the same input. – Whenever R calls Aideal , send it x1 , . . . , xm (if R queries G during this call then query it as well). Let z = (z1 , . . . , zm ) ∈ {0, 1}m denote the respective answers of R. Call Areal (1n , z, G), where G is the current set of query-answer pairs with respect to G, and send to R the same answer. 2. Output whatever R outputs. ............................................................................. e and R output the same value with high probability. We next show that R We do so by showing that the statistical distance between the states of R and e after every call to the adversary is small. Towards proving this, we first show R that for every possible sequence of responses z made by the reduction, the two scores computed by the real and ideal adversaries at any given call are somewhat close except with a negligible probability, where the probability is taken over G and y ∗ (the randomness of the reduction is fixed). In the following, for a set G G ⊆ {0, 1}n × {0, 1}n+r we let Fn,n+r denote the set of all functions that are consistent with G. Lemma 3. Consider a call made by the reduction to the distinguishing oracle, and fix the query-answer pairs G ⊆ {0, 1}n × {0, 1}n+r made so far by the reduction. Let Y denote the distribution over {0, 1}n+r for the challenge given to 21

the reduction (i.e., it is either uniform over {0, 1}n+r or is G(S) for S uniform over {0, 1}n ), and let z ∈ ({0, 1})m denote the reduction’s answers to the distinguishing oracle on inputs x1 , . . . , xm . Then for every δ ≥ 2/ν, PrG←F G

n,n+r ,y

∗ ←Y

2   G λ− δ2 ·ν . ∃k ∈ {0, 1}λ : isG k (z) − rsk (z) ≥ δ · |Ik | ≤ e

(3)

Proof. By the union bound, it suffices to show that PrG←F G

∗ n,n+r ,y ←Y



2  G − δ2 ·ν isG k (z) − rsk (z) ≥ δ · |Ik | ≤ e

(4)

for every key k ∈ {0, 1}λ . As noted before, if ℓ(k) = c, then the two scores are identical and the difference is 0. In the remainder of the proof, we assume that ℓ(k) < c. For every y ∈ ({0, 1}n+r )ℓ(k) , let  G isG i ∈ Ik : fk,s (xi ) = zi k (z, y) = k ,y and let rsGk (z, y) =

X

h ′ i G PrG′ ←Fn,n+r fk,(s (x ) = z G G i i , k ||s ),(y||y )

i∈Ik

where sG is the sequence of seeds in G that do not appear in sk , and yG is the sequence of corresponding outputs. We show that for any sequence y ∈ ({0, 1}n+r )ℓ(k) , PrG←F G

n,n+r ,y

∗ ←Y



2  G − δ2 ·ν . isG k (z, y) − rsk (z, y) ≥ δ · |Ik | ≤ e

(5)

In particular, this holds for the y that maximizes the scores, which implies Equation (4). Note that the string y that maximizes the scores for the real and ideal adversaries could be different, but Equation (5) implies Equation (4) nevertheless. Fixing k and y ∈ ({0, 1}n+r )ℓ(k) , we simplify notation by writing is and rs for the ideal and real scores, respectively. We next show that rs ≤ EG←F G

n,n+r ,y

∗ ←Y

[is] ≤ rs + 1.

(6)

By linearity of expectation, it follows that the contribution of every i ∈ Ik to EG [is] is  G  PrG←F G ,y ∗ ←Y fk,sk ,y (xi ) = zi n,n+r

∗

(where zi may depend on y and G). If Y is the uniform distribution over {0, 1}n+r , then PrG←F G

n,n+r

,y ∗ ←Y

 G  fk,sk ,y (xi ) = zi = PrG′ ←F G

n,n+r

,y ∗ ←Y

h ′ i G fk,(s (x ) = z G G i i k ||s ),(y||y )

for every i ∈ Ik , hence EG,y∗ [is] = rs. Otherwise, if the distribution of Y is G(S) where S is uniform over {0, 1}n , then every i ∈ Ik such that zi = P (xi , k, y′ ), 22

where Y appears in y′ , contributes 1 to EG,y∗ [is]. Since the sets {Sj (xi , k) : j ∈ [c]} are pairwise disjoint, there is at most 1 such i. On the other hand, for the real score, each i contributes a value between 0 and 1, thus EG,y∗ [is] ≤ rs + 1. G For every i ∈ Ik let Xi denote the indicator for the event fk,s (xi ) = zi k ,y P G (over sampling G ← Fn,n+r and y ∗ ← Y ). Then is = i∈Ik Xi . These random variables are independent since the sets {Sj (xi , k) : j ∈ [c]} are pairwise disjoint. Since δ ≥ 2/ν ≥ 2/|Ik |, by Hoeffding’s inequality, it follows that PrG←F G

n,n+r ,y

∗ ←Y

≤ PrG←F G

[|is − rs| ≥ δ · |Ik |]

[|is − E [is]| ≥ δ · |Ik | − 1]   δ · |I | ≤ PrG←F G |is − E [is]| ≥ ∗ k n,n+r ,y ←Y 2 2 2( δ ·|Ik |) − 2 Ik | | ≤e n,n+r ,y

∗ ←Y

δ2

= e− 2 ·|Ik | . □ We now show that for any call by the reduction to the distinguishing oracle, the statistical distance (taken over G and the challenge y ∗ ) between the answers of Aideal and Areal is small. Lemma 4. Fix a call to the distinguishing oracle. Let G ⊆ {0, 1}n × {0, 1}n+r denote the set of query-answer pairs made by R to G, let Y denote the distribution over the challenge, and let z = (z1 , . . . , zm ) ∈ {0, 1}m denote the answers of R when receiving inputs x1 , . . . , xm from the distinguishing oracle. Finally, ∗ G for every G ∈ Fn,n+r and y ∗ ∈ {0, 1}n+r let ipG,y denote the probability that ∗ Aideal (1n ) outputs 1 when given z as the oracle answers, and let rpG,y denote the probability that Areal (1n , z, G) outputs 1. Then, for every δ ≥ 2/ν   ∗ δ2 G,y ∗ , rpG,y ≤ eλ− 2 ·ν + 5δ. SDG←F G ,y ∗ ←Y ip n,n+r

G Proof. For every G ∈ Fn,n+r and every y ∗ ∈ {0, 1}n+r let ∗

G isG k (z) − rsk (z) . |Ik | k∈{0,1}λ

µG,y = max

Additionally, for every α ∈ [0.8, 1] let ( 1 if ∃k ∈ {0, 1}λ : isG k (z) ≥ α|Ik | G,y ∗ ip (α) = 0 otherwise, and let rp

G,y ∗

( 1 if ∃k ∈ {0, 1}λ : rsGk (z) ≥ α|Ik | (α) = 0 otherwise. 23

Then by Jensen’s inequality, i h h i ∗ ∗ ∗ ∗ Eα←[0.8,1] ipG,y (α) − rpG,y (α) ≤ Eα←[0.8,1] ipG,y (α) − rpG,y (α) . Note that any α contributes to the expectation on the right-hand side if and only G ′ if α is between isG k (z)/|Ik | and rsk′ (z)/|Ik′ ,ℓ′ (k′ ) | for (possibly distinct) k, k ∈ λ G,y ∗ {0, 1} . Observe that this distance is at most µ (i.e., the distance with respect to the same key). Therefore, i h ∗ ∗ Eα←[0.8,1] ipG,y (α) − rpG,y (α) " #  G  G G max isG k (z), rsk (z) λ min isk (z), rsk (z) ≤ Prα←[0.8,1] ∃k ∈ {0, 1} : ≤α≤ |Ik | |Ik | ∗

µG,y 1 − 0.8 ∗ = 5µG,y . ≤

Hence, by Lemma 3, h

PrG←F G

h i i ∗ ∗ Eα ipG,y (α) − rpG,y (α) ≥ 5δ   λ G G ,y ∗ ←Y ∃k ∈ {0, 1} : isk (z) − rsk (z) ≥ δ · |Ik |

∗ n,n+r ,y ←Y

≤ PrG←F G

n,n+r

2

λ− δ2 ·ν

≤e

.

Therefore, the statistical distance is bounded by   Gy ∗ G,y ∗ ip , rp SDG←F G ∗ n,n+r ,y ←Y h i ∗ ∗ ipG,y − rpG,y ≤ EG←F G ∗ ←Y ,y n,n+r h h ii G,y ∗ G,y ∗ E ip (α) − rp (α) = EG←F G ∗ α n,n+r ,y ←Y h h i i ∗ ∗ ≤ PrG←Fn,n+r ,y∗ ←Y Eα ipG,y (α) − rpG,y (α) ≥ 5δ + 5δ δ2

≤ eλ− 2 ·ν + 5δ. □ e For every t ∈ {0, 1, . . . , d}, let stt and sett denote the states of R and R, th respectively, after the t call to the distinguishing oracle, where the state consists of, the challenge y ∗ , the (current) query-answer pairs G made to the PRG, and the t answers of the distinguishing oracle.9 Then by Lemma 4 and the triangle inequality, for every t ∈ [d], after the tth call to the distinguishing oracle,

δ2 δ2 SD stt , sett ≤ SD stt−1 , sett−1 + eλ− 2 ·ν + 5δ ≤ t · eλ− 2 ·ν + 5tδ, 9 Formally, it should also depend on the randomness. Since all our claims hold for every randomness, we ignore it for simplicity.

24

G where the statistical distances are taken over G ← Fn,n+r , y ∗ ← Y where Y is the distribution of the challenge, and over the reductions’ randomness. Thus,

i h 2 eG (y ∗ ) ̸= RAideal ,G (y ∗ ) ≤ d · eλ− δ2 ·ν + 5dδ, Pr R

(7)

G where the probability is taken over G ← Fn,n+r , y ∗ ← Y where Y is the distribution of the challenge, and over the reductions’ randomness.

Step 4: Putting it all together. Our goal is to upper-bound 

 h i eG (1n , G(s)) = 1 Prs←{0,1}n R   ∆ := PrG←Fn,n+r  i h  1 G n e (1 , y) = 1 ≤ −Pry←{0,1}n+r R γ 3n Towards bounding ∆, we first upper-bound the expected difference between e (where the expectation is taken over G). To alleviate nothe answers of R and R tations, throughout the rest of the proof we remove Aideal from the notations and write RG instead. Additionally, all probabilities are taken over the reductions’ randomness and we ignore this for brevity.

Claim 11. Let Y denote the distribution over the challenge. Then for all sufficiently large n’s, EG←Fn,n+r

h

h i 2  i eG (y ∗ ) = 1 − Pry∗ ←Y RG (y ∗ ) = 1 ≤ d·eλ− δ2 ·ν +5dδ. Pry∗ ←Y R

Proof. For every G ∈ Fn,n+r , observe that h i h i   eG (y ∗ ) = 1 ≤ Pry∗ ←Y RG (y ∗ ) = 1 + Pry∗ ←Y R eG (y ∗ ) ̸= RG (y ∗ ) Pry∗ ←Y R and that h i h i   eG (y ∗ ) = 1 ≥ Pry∗ ←Y R eG (y ∗ ) = RG (y ∗ ) · Pry∗ ←Y RG (y ∗ ) = 1 . Pry∗ ←Y R Let Fe denote the set of all functions in Fn,n+r such that h i   eG (y ∗ ) = 1 ≥ Pry∗ ←Y RG (y ∗ ) = 1 . Pry∗ ←Y R 25

Then h i  i eG (y ∗ ) = 1 − Pry∗ ←Y RG (y ∗ ) = 1 Pry∗ ←Y R h i X   1 eG (y ∗ ) = 1 − Pry∗ ←Y RG (y ∗ ) = 1 ≤ 2n (n+r) · Pry∗ ←Y R 2 e G∈F  h i X   1 eG (y ∗ ) = 1 Pry∗ ←Y RG (y ∗ ) = 1 − Pry∗ ←Y R + 2n (n+r) · 2 e G∈Fn,n+r \F h i X 1 eG (y ∗ ) ̸= RG (y ∗ ) ≤ 2n (n+r) · Pry∗ ←Y R 2 e G∈F h i X   1 eG (y ∗ ) ̸= RG (y ∗ ) + 2n (n+r) · Pry∗ ←Y RG (y ∗ ) = 1 · Pry∗ ←Y R 2 e G∈Fn,n+r \F h h ii eG (y ∗ ) ̸= RG (y ∗ ) ≤ EG←Fn,n+r Pry∗ ←Y R

EG←Fn,n+r

h

δ2

≤ d · eλ− 2 ·ν + 5dδ, where the last inequality follows from Equation (7).

□

Now, observe that    Prs←{0,1}n RG (1n , G(s)) = 1 ∆ ≤PrG←Fn,n+r    1  −Pry←{0,1}n+r RG (1n , y) = 1 < γ n     Prs←{0,1}n RG (1n , G(s)) = 1 i h  + PrG←Fn,n+r  eG (1n , G(s)) = 1 > 1 −Prs←{0,1}n R 3nγ   G n  Pry←{0,1}n+r R (1 , y) = 1 h i . + PrG←Fn,n+r  eG (1n , y) = 1 > 1 −Pry←{0,1}n+r R 3nγ 

Note that by Equation (1), the first term is 0 for infinitely many n’s. As for the other two terms, by Markov’s inequality and Claim 11, it follows that both terms are upper-bounded by   δ2 3nγ · d · eλ− 2 ·ν + 5dδ . We conclude that

  δ2 ∆ ≤ 6nγ · d · eλ− 2 ·ν + 5dδ

for infinitely many n’s. We next choose the parameters such that ∆ ≤ 3/4 for infinitely many n’s. Specifically, we choose δ and √ ν (which we later translate to choosing mt for every t ∈ [c]). Let δ = 1/48dnγ 4 ν and let ν = 2(λ + n) · d2 n2γ . Then δ ≥ 2/ν and 26

δ2

ν ≥ 2(λ + n)/δ 2 if ν is sufficiently large. In this case, eλ− 2 ·ν ≤ e−n . Since ν is a polynomial of n, ν ≤ 2den for all sufficiently large n’s. Therefore δ ≥ 2/ν ≥ e−n /d, hence e−n ≤ dδ. Thus, for such choices of ν, ∆ ≤ 36dnγ · δ ≤ 3/4. Now, recall that ν = mink∈{0,1}λ |Ik |, and that for every k ∈ {0, 1}λ , either mt−1 for some t ∈ [c]. Further recall that for Aideal to |Ik | = mc or |Ik | = (c−t)m t −n be have 1 − e advantage, we took mc ≥ 10(λ + c(n + r) + n) and mt−1 ≥ (c − t + 1)mt · 10(λ + c(n + r) + n) for all t ∈ [c]. Therefore, we let10 mc = 10(λ + c(n + r) + n) + 2(λ + n) · d2 n2γ and
mt−1 = (c − t + 1) 10(λ + c(n + r) + n) + 2(λ + n) · d2 n2γ · mt for every t ∈ [c]. As a result, the adversaries query the function on m = m0 ≤ nαc · c! inputs, for some constant α ∈ N.11 . Since there are 2in possible inputs, for the adversaries to be well-defined, it must be the case where nαc · c! ≤ 2in . in Indeed, since c = w(n)·log in for some w(n) = ω(1), in

in

nαc · c! ≤ nαc · cc = 2αc log n+c log c ≤ 2α w(n) log in log n+ w(n) log in log in ≤ 2in , for all sufficiently large n’s, where the last inequality is due to the fact that in = poly(n), hence log n = O(log in). Finally, in order to contradict Lemma 1, we show that the total number of e makes to G is at most 2n/4 . Indeed, in each of the d calls to the queries R distinguishing oracle, the number of calls to G that the reduction makes is at most poly(m) ≤ nβc · (c!)β ≤ nβc · cβc = 2βc log n+βc log c n for some constant β ∈ N. Recall that c = w(n)·log n , where w(n) = ω(1). Theree makes is at most fore, the total number of calls that R βn

βn

n

2βn

d · 2βc log n+βc log c = d · 2 w(n) + w(n) log n log w(n) log n ≤ d · 2 w(n) ≤ 2n/4 , for sufficiently large n’s.

□

Remark 1 (On the definition of black-box reduction). In the definition we considered, the advantage of the reduction R is a polynomial of the advantage of the distinguishing oracle A. This in particular allowed us to conclude the existence of γ ∈ N for which Equation (1) holds. In the definition for black box constructions of PRF from Beimel et al. [2], it is only required that if A succeeds with noticeable probability, then so does R. Under this definition, Equation (1) does 10

The bound on mc can be improved to 10(λ + c(n + r) + n). This is because the other term comes from considering k’s such that ℓ(k) < c (recall that if ℓ(k) = c then both scores are identical). 11 α depends on the degree of the polynomials λ, r, d, and γ.

27

not necessarily hold, since the advantage of R might decrease as a function of the advantage of A. Nevertheless, to the best of our knowledge, all black-box reductions studied in the literature satisfy the stronger requirement. Moreover, our proof continues to hold under the weaker assumption that the advantage of R is bounded below for all distinguishing oracles with a sufficiently large advantage.

5

Lower Bounds for Black-Box Constructions of a PRF With a Long Output

In this section, we show our lower bounds for fully black-box constructions of PRF with a long output from a PRG, with adaptive calls. We will use the following result, stating the existence of a PRG with respect to some oracle f . Lemma 5 ([2, Lemma 3.5]). For every oracle f = {fn : {0, 1}n → {0, 1}n }n∈N and w, r : N → N such r(n) = 2o(w(n)) , there exists a (possibly ineffi that n +w(n) cient) function G = Gn : {0, 1} → {0, 1}n+r(n) n∈N such that the following holds. For every ppt oracle-aided algorithm A, there exists a negligible function µ such that     Prs←{0,1}w(n) Af,G (1n , G (1n , s)) = 1 − Pry←{0,1}n+r(n) Af,G (1n , y) = 1 ≤ µ(n). In what follows, we refer to the function G as the PRG with respect to the oracle f . We are now ready to state and prove our lower bound on the number of calls to the PRG required to construct a PRF with a long output. Throughout the section we fix the input length in = in(n), the output length out = out(n), the key length λ = λ(n), and the PRG stretch r = r(n). out Theorem 12. For every c(n) = r+ω(log n) , there is no c(n)-call fully black-box construction of a weak PRF with output length out from an r-bit stretch PRG.

Proof. Fix w = w(n) = ω(log n) and let c = c(n) = out/(r +w). Assume towards contradiction that there exists a c-call fully black-box construction (F, R) from an r-bit stretch PRG, where n o (·) F = fk : {0, 1}in → {0, 1}out . λ n∈N,k∈{0,1}

That is, for every i ∈ [c] there exist Si : {0, 1}in × {0, 1}λ × ({0, 1}(n+r) )i−1 → c {0, 1}n , and there exists P : {0, 1}m × {0, 1}λ × ({0, 1}n+r ) → {0, 1}out such that fkG (x) = P (x, k, G (s1 ) , . . . , G(sc )) for all G : {0, 1}n → {0, 1}n+r , where si = Si (x, k, G (s1 ) , . . . , G(si−1 )) for all i ∈ [c]. To obtain a contradiction, we consider a PRG that is applied only to the first w bits of the seed. This, intuitively, implies that the entropy of the output of 28

the PRF over m inputs is provided only by the key (which has λ entropy) and m · (w + r) · c additional bits from all applications of the r-bit stretch PRG. On the other hand, for a random function, the amount of entropy is m · out. Taking m = (n + λ)/c results in a large gap between the two cases. In the following, for a string s = (s1 , . . . , sn ) ∈ {0, 1}n and i ∈ [n] we let s<i = (s1 , . . . , si−1 ) and let s≥i = (si , . . . , sn ). We use || to denote the concatenation of strings. We first define a distinguisher A(·) for the PRF. .............................................................................. Algorithm 13 (A). Input: The security parameter 1n . Oracle access: A function f : {0, 1}in → {0, 1}out . 1. Let m = m(n) = (n + λ)/c and let x1 , . . . , xm ∈ {0, 1}in denote the lexicographically first m inputs.12 2. Query f on x1 , . . . , xm , and let z1 , . . . , zm ∈ {0, 1}out denote the respective answers. 3. Output 1 if and only if there exists k ∈ {0, 1}λ and (yi,j )i∈[m],j∈[c] ∈ ({0, 1}w+r−1 )m·c such that P (xi , k, (yi,1 ||si,1 ) , . . . , (yi,c ||si,c )) = zi for all i ∈ [m], where si,j = Sj (xi , k, (yi,1 ||si,1 ) , . . . , (yi,j−1 ||si,j−1 ))≥ out −r c

For all i ∈ [m] and j ∈ [c]. ............................................................................. We next define a PRG for which A breaks the security of F . Since w = ω(log n) and r is a polynomial, it follows that n+r = 2o(w−1) . Thus, by Lemma 5 there exists a PRG G′ : {0, 1}w−1 → {0, 1}w+r−1 with respect to the oracle A, that cannot be broken with non-negligible probability. Consider the PRG G : {0, 1}n → {0, 1}n+r defined as G(s) = G′ (s<w ) ||s≥w . G

Observe that Afk always outputs 1. To reach a contradiction, we next show that for a random function f , this probability is at most 2−n . Indeed, by the union

12 Note that if we obtain a contradiction for all distinct inputs, then the same holds for random inputs, up to the birthday bound.

29

bound,   Prf ←Fin Af (1n ) = 1  
m·c ∀i ∈ [m] : ∃k ∈ {0, 1}λ ∃ (yi,j )i∈[m],j∈[c] ∈ {0, 1}w+r−1    = Prf ←Fin  c P xi , k, (yi,j ||si,j )j=1 = f (xi )  i h  c ≤ 2λ+m·c·(w+r−1) · Prf ←Fin ∀i ∈ [m] : P xi , k, (yi,j ||si,j )j=1 = f (xi ) 2λ+m·out−m·c 2m·out −n =2 .

=

Since (F, R) is assumed to be a fully black-box PRF construction, it follows that eA,G′ RA,G breaks G. However, this implies the existence of a ppt algorithm R ′ breaking G , contradicting Lemma 5. □

30

Bibliography

[1] P. Baecher, C. Brzuska, and M. Fischlin. Notions of black-box reductions, revisited. In K. Sako and P. Sarkar, editors, Advances in Cryptology - ASIACRYPT 2013 - 19th International Conference on the Theory and Application of Cryptology and Information Security, Bengaluru, India, December 1-5, 2013, Proceedings, Part I, volume 8269 of Lecture Notes in Computer Science, pages 296–315. Springer, 2013. [2] A. Beimel, T. Malkin, and N. Mazor. Structural lower bounds on black-box constructions of pseudorandom functions. In L. Reyzin and D. Stebila, editors, Advances in Cryptology - CRYPTO 2024 - 44th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 18-22, 2024, Proceedings, Part V, volume 14924 of Lecture Notes in Computer Science, pages 459–488. Springer, 2024. [3] M. Bellare and P. Rogaway. The security of triple encryption and a framework for code-based game-playing proofs. In Proceedings of the 24th Annual International Conference on The Theory and Applications of Cryptographic Techniques, EUROCRYPT’06, page 409–426, Berlin, Heidelberg, 2006. Springer-Verlag. ISBN 3540345469. [4] I. Berman and I. Haitner. From non-adaptive to adaptive pseudorandom functions. In R. Cramer, editor, Theory of Cryptography - 9th Theory of Cryptography Conference, TCC 2012, Taormina, Sicily, Italy, March 1921, 2012. Proceedings, volume 7194 of Lecture Notes in Computer Science, pages 357–368. Springer, 2012. [5] D. Boneh and R. Venkatesan. Breaking RSA may not be equivalent to factoring. In K. Nyberg, editor, Advances in Cryptology - EUROCRYPT ’98, International Conference on the Theory and Application of Cryptographic Techniques, Espoo, Finland, May 31 - June 4, 1998, Proceeding, volume 1403 of Lecture Notes in Computer Science, pages 59–71. Springer, 1998. [6] E. Bresson, J. Monnerat, and D. Vergnaud. Separation results on the "onemore" computational problems. In T. Malkin, editor, Topics in Cryptology - CT-RSA 2008, The Cryptographers’ Track at the RSA Conference 2008, San Francisco, CA, USA, April 8-11, 2008. Proceedings, volume 4964 of Lecture Notes in Computer Science, pages 71–87. Springer, 2008. [7] M. Fischlin and D. Schröder. On the impossibility of three-move blind signature schemes. In H. Gilbert, editor, Advances in Cryptology - EUROCRYPT 2010, 29th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Monaco / French Riviera, May 30 - June 3, 2010. Proceedings, volume 6110 of Lecture Notes in Computer Science, pages 197–215. Springer, 2010. [8] R. Gennaro and L. Trevisan. Lower bounds on the efficiency of generic cryptographic constructions. In 41st Annual Symposium on Foundations of Computer Science, FOCS 2000, Redondo Beach, California, USA, November 12-14, 2000, pages 305–313. IEEE Computer Society, 2000.

[9] O. Goldreich and L. A. Levin. A hard-core predicate for all one-way functions. In D. S. Johnson, editor, Proceedings of the 21st Annual ACM Symposium on Theory of Computing, May 14-17, 1989, Seattle, Washington, USA, pages 25–32. ACM, 1989. [10] O. Goldreich, S. Goldwasser, and S. Micali. How to construct random functions. Journal of the ACM (JACM), 33(4):792–807, 1986. [11] I. Haitner, A. Rosen, and R. Shaltiel. On the (im)possibility of arthur-merlin witness hiding protocols. In O. Reingold, editor, Theory of Cryptography, 6th Theory of Cryptography Conference, TCC 2009, San Francisco, CA, USA, March 15-17, 2009. Proceedings, volume 5444 of Lecture Notes in Computer Science, pages 220–237. Springer, 2009. [12] R. Impagliazzo and S. Rudich. Limits on the provable consequences of one-way permutations. In D. S. Johnson, editor, Proceedings of the 21st Annual ACM Symposium on Theory of Computing, May 14-17, 1989, Seattle, Washington, USA, pages 44–61. ACM, 1989. [13] L. A. Levin. One-way functions and pseudorandom generators. In Proceedings of the seventeenth annual ACM symposium on Theory of computing, pages 363–365, 1985. [14] E. Miles and E. Viola. On the complexity of non-adaptively increasing the stretch of pseudorandom generators. In Y. Ishai, editor, Theory of Cryptography - 8th Theory of Cryptography Conference, TCC 2011, Providence, RI, USA, March 28-30, 2011. Proceedings, volume 6597 of Lecture Notes in Computer Science, pages 522–539. Springer, 2011. [15] E. Miles and E. Viola. On the complexity of constructing pseudorandom functions (especially when they don’t exist). J. Cryptol., 28(3):509–532, 2015. [16] R. Pass. Limits of provable security from standard assumptions. In L. Fortnow and S. P. Vadhan, editors, Proceedings of the 43rd ACM Symposium on Theory of Computing, STOC 2011, San Jose, CA, USA, 6-8 June 2011, pages 109–118. ACM, 2011. [17] R. Pass. Unprovable security of perfect NIZK and non-interactive nonmalleable commitments. In A. Sahai, editor, Theory of Cryptography - 10th Theory of Cryptography Conference, TCC 2013, Tokyo, Japan, March 36, 2013. Proceedings, volume 7785 of Lecture Notes in Computer Science, pages 334–354. Springer, 2013. [18] O. Reingold, L. Trevisan, and S. P. Vadhan. Notions of reducibility between cryptographic primitives. In M. Naor, editor, Theory of Cryptography, First Theory of Cryptography Conference, TCC 2004, Cambridge, MA, USA, February 19-21, 2004, Proceedings, volume 2951 of Lecture Notes in Computer Science, pages 1–20. Springer, 2004. [19] P. Soni and S. Tessaro. On the query complexity of constructing prfs from non-adaptive prfs. In C. Galdi and V. Kolesnikov, editors, Security and Cryptography for Networks - 12th International Conference, SCN 2020, Amalfi, Italy, September 14-16, 2020, Proceedings, volume 12238 of Lecture Notes in Computer Science, pages 546–565. Springer, 2020. 32

[20] B. Waters. Efficient identity-based encryption without random oracles. In R. Cramer, editor, Advances in Cryptology - EUROCRYPT 2005, 24th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Aarhus, Denmark, May 22-26, 2005, Proceedings, volume 3494 of Lecture Notes in Computer Science, pages 114–127. Springer, 2005.

33

Related documents

• Lower Bounds on Black-Box Constructions of Pseudorandom Functions#609661
• Exact Minimax One-Bit Unbiased Compression: Heavy-Tail Necessity and Finite-Randomness Approximation#1064404
• Algorithmic Randomness, Exchangeability, and the Principal Principle#694494
• Spoofing Missed-Detection Bounds for PRF GNSS Ranging Authentication Under AWGN Models#1036582
• Complexity Theory of Randomised Testing#363312