International Association
for Cryptologic Research

We address the black-box complexity of constructing pseudorandom functions (PRF) from pseudorandom generators (PRG). The celebrated GGM construction of Goldreich, Goldwasser, and Micali (Crypto 1984) provides such a construction, which (even when combined with Levin's domain-extension trick) has super-logarithmic depth. Despite many years and much effort, this remains essentially the best construction we have to date. On the negative side, one step is provided by the work of Miles and Viola (TCC 2011), which shows that a black-box construction which just calls the PRG once and outputs one of its output bits, cannot be a PRF. In this work, we make significant further progress: we rule out black-box constructions of PRF from PRG that follow certain structural constraints, but may call the PRG adaptively polynomially many times. In particular, we define ``tree constructions" which generalize the GGM structure: they apply the PRG $G$ along a tree path, but allow for different choices of functions to compute the children of a node on the tree and to compute the next node on the computation path down the tree. We prove that a tree construction of logarithmic depth cannot be a PRF (while GGM is a tree construction of super-logarithmic depth). Moreover, we prove that there is no PRF construction that uses such a tree construction (returning one bit) as an oracle, even if allowed to call the oracle adaptively polynomially many times with a different input (root value) each time. We also show several other results and discuss the special case of one-call constructions. Our main results in fact rule out even weak PRF constructions with one output bit. We use the oracle separation methodology introduced by Gertner, Malkin, and Reingold (FOCS 2001), and show that for any candidate black-box construction F^G from G, there exists an oracle relative to which G is a PRG, but F^G is not a PRF.

<jats:title>Abstract</jats:title><jats:p>Two of the most useful cryptographic primitives that can be constructed from one-way functions are <jats:italic>pseudorandom generators</jats:italic> (PRGs) and <jats:italic>universal one-way hash functions</jats:italic> (UOWHFs). In order to implement them in practice, the efficiency of such constructions must be considered. The three major efficiency measures are: the <jats:italic>seed length</jats:italic>, the <jats:italic>call complexity</jats:italic> to the one-way function, and the <jats:italic>adaptivity</jats:italic> of these calls. Still, the optimal efficiency of these constructions is not yet fully understood: there exist gaps between the known upper bound and the known lower bound for black-box constructions. A special class of one-way functions called <jats:italic>unknown-regular</jats:italic> one-way functions is much better understood. Haitner, Harnik and Reingold (CRYPTO 2006) presented a PRG construction with semi-linear seed length and linear number of calls based on a method called <jats:italic>randomized iterate</jats:italic>. Ames, Gennaro and Venkitasubramaniam (ASIACRYPT 2012) then gave a construction of UOWHF with similar parameters and using similar ideas. On the other hand, Holenstein and Sinha (FOCS 2012) and Barhum and Holenstein (TCC 2013) showed an almost linear call-complexity lower bound for black-box constructions of PRGs and UOWHFs from one-way functions. Hence, Haitner et al. and Ames et al. reached <jats:italic>tight</jats:italic> constructions (in terms of seed length and the number of calls) of PRGs and UOWHFs from regular one-way functions. These constructions, however, are adaptive. In this work, we present non-adaptive constructions for both primitives which match the optimal call complexity given by Holenstein and Sinha and Barhum and Holenstein. Our constructions, besides being simple and non-adaptive, are robust also for <jats:italic>almost-regular</jats:italic> one-way functions.</jats:p>

Two of the most useful cryptographic primitives that can be constructed from one-way functions are pseudorandom generators (PRGs) and universal one-way hash functions (UOWHFs). The three major efficiency measures of these primitives are: seed length, number of calls to the one-way function, and adaptivity of these calls. Although a long and successful line of research studied these primitives, their optimal efficiency is not yet fully understood: there are gaps between the known upper bounds and the known lower bounds for black-box constructions. Interestingly, the first construction of PRGs by H ̊astad, Impagliazzo, Levin, and Luby [SICOMP ’99], and the UOWHFs construction by Rompel [STOC ’90] shared a similar structure. Since then, there was an improvement in the efficiency of both constructions: The state-of-the-art construction of PRGs by Haitner, Reingold, and Vadhan [STOC ’10] uses O(n^4) bits of random seed and O(n^3) non-adaptive calls to the one-way function, or alternatively, seed of size O(n^3) with O(n^3) adaptive calls (Vadhan and Zhen [STOC ’12]). Constructing a UOWHF with similar parameters is still an open question. Currently, the best UOWHF construction by Haitner, Holenstein, Reingold, Vadhan, and Wee [Eurocrypt ’10] uses O(n^13) adaptive calls and a key of size O(n^5). In this work we give the first non-adaptive construction of UOWHFs from arbitrary one-way functions. Our construction uses O(n^9) calls to the one-way function, and a key of length O(n^10). By the result of Applebaum, Ishai, and Kushilevitz [FOCS ’04], the above implies the existence of UOWHFs in NC0, given the existence of one-way functions in NC1. We also show that the PRG construction of Haitner et al., with small modifications, yields a relaxed notion of UOWHFs. In order to analyze this construction, we introduce the notion of next-bit unreachable entropy, which replaces the next-bit pseudoentropy notion, used in the PRG construction above.

A central result in the theory of Cryptography, by Hastad, Imagliazzo, Luby and Levin [SICOMP’99], demonstrates that the existence one-way functions (OWF) implies the existence of pseudo-random generators (PRGs). Despite the fundamental importance of this result, and several elegant improvements/simplifications, analyses of constructions of PRGs from OWFs remain complex (both conceptually and technically). Our goal is to provide a construction of a PRG from OWFs with a simple proof of security; we thus focus on the setting of non-uniform security (i.e., we start off with a OWF secure against non-uniform PPT, and we aim to get a PRG secure against non-uniform PPT). Our main result is a construction of a PRG from OWFs with a self-contained, simple, proof of security, relying only on the Goldreich-Levin Theorem (and the Chernoff bound). Although our main goal is simplicity, the construction, and a variant there-of, also improves the efficiency—in terms of invocations and seed lengths—of the state-of-the-art constructions due to [Haitner-Reingold-Vadhan, STOC’10] and [Vadhan-Zheng, STOC’12], by a factor O(log2 n). The key novelty in our analysis is a generalization of the Blum-Micali [FOCS’82] notion of unpredictabilty—rather than requiring that every bit in the output of a function is unpredictable, we count how many unpredictable bits a function has, and we show that any OWF on n input bits (after hashing the input and the output) has n + O(log n) unpredictable output bits. Such unpredictable bits can next be “extracted” into a pseudorandom string using standard techniques.

Two of the most useful cryptographic primitives that can be constructed from one-way functions are pseudorandom generators (PRGs) and universal one-way hash functions (UOWHFs). In order to implement them in practice, the efficiency of such constructions must be considered. The three major efficiency measures are: the seed length, the call complexity to the one-way function, and the adaptivity of these calls. Still, the optimal efficiency of these constructions is not yet fully understood: there exist gaps between the known upper bound and the known lower bound for black-box constructions. A special class of one-way functions called unknown-regular one-way functions is much better understood. Haitner, Harnik and Reingold (CRYPTO 2006) presented a PRG construction with semi-linear seed length and linear number of calls based on a method called randomized iterate. Ames, Gennaro and Venkitasubramaniam (TCC 2012) then gave a construction of UOWHF with similar parameters and using similar ideas. On the other hand, Holenstein and Sinha (FOCS 2012) and Barhum and Holenstein (TCC 2013) showed an almost linear call-complexity lower bound for black-box constructions of PRGs and UOWHFs from one-way functions. Hence Haitner et al. and Ames et al. reached tight constructions (in terms of seed length and the number of calls) of PRGs and UOWHFs from regular one-way functions. These constructions, however, are adaptive. In this work, we present non-adaptive constructions for both primitives which match the optimal call-complexity given by Holenstein and Sinha and Barhum and Holenstein. Our constructions, besides being simple and non-adaptive, are robust also for almost-regular one-way functions.

We study time/memory tradeoffs of function inversion: an algorithm, i.e., an inverter, equipped with an s-bit advice on a randomly chosen function f:[n]->[n] and using q oracle queries to f, tries to invert a randomly chosen output y of f (i.e., to find x such that f(x)=y). Much progress was done regarding adaptive function inversion - the inverter is allowed to make adaptive oracle queries. Hellman [IEEE transactions on Information Theory '80] presented an adaptive inverter that inverts with high probability a random f. Fiat and Naor [SICOMP '00] proved that for any s,q with s^3 q = n^3 (ignoring low-order terms), an s-advice, q-query variant of Hellman's algorithm inverts a constant fraction of the image points of any function. Yao [STOC '90] proved a lower bound of sq<=n for this problem. Closing the gap between the above lower and upper bounds is a long-standing open question. Very little is known of the non-adaptive variant of the question - the inverter chooses its queries in advance. The only known upper bounds, i.e., inverters, are the trivial ones (with s+q=n), and the only lower bound is the above bound of Yao. In a recent work, Corrigan-Gibbs and Kogan [TCC '19] partially justified the difficulty of finding lower bounds on non-adaptive inverters, showing that a lower bound on the time/memory tradeoff of non-adaptive inverters implies a lower bound on low-depth Boolean circuits. Bounds that, for a strong enough choice of parameters, are notoriously hard to prove. We make progress on the above intriguing question, both for the adaptive and the non-adaptive case, proving the following lower bounds on restricted families of inverters: Linear-advice (adaptive inverter): If the advice string is a linear function of f (e.g., A*f, for some matrix A, viewing f as a vector in [n]^n), then s+q is \Omega(n). The bound generalizes to the case where the advice string of f_1 + f_2, i.e., the coordinate-wise addition of the truth tables of f_1 and f_2, can be computed from the description of f_1 and f_2 by a low communication protocol. Affine non-adaptive decoders: If the non-adaptive inverter has an affine decoder - it outputs a linear function, determined by the advice string and the element to invert, of the query answers - then s is \Omega(n) (regardless of q). Affine non-adaptive decision trees: If the non-adaptive inverter is a d-depth affine decision tree - it outputs the evaluation of a decision tree whose nodes compute a linear function of the answers to the queries - and q < cn for some universal c>0, then s is \Omega(n/d \log n).

Consider a ppt two-party protocol $$\varPi = (\mathsf {A} ,\mathsf {B} )$$ in which the parties get no private inputs and obtain outputs $$O^{\mathsf {A} },O^{\mathsf {B} }\in \left\{ 0,1\right\} $$, and let $$V^\mathsf {A} $$ and $$V^\mathsf {B} $$ denote the parties’ individual views. Protocol $$\varPi $$ has $$\alpha $$-agreement if $$\Pr [O^{\mathsf {A} }=O^{\mathsf {B} }] = \tfrac{1}{2}+\alpha $$. The leakage of $$\varPi $$ is the amount of information a party obtains about the event $$\left\{ O^{\mathsf {A} }=O^{\mathsf {B} }\right\} $$; that is, the leakage$$\epsilon $$ is the maximum, over $$\mathsf {P} \in \left\{ \mathsf {A} ,\mathsf {B} \right\} $$, of the distance between $$V^\mathsf {P} |_{O^{\mathsf {A} }= O^{\mathsf {B} }}$$ and $$V^\mathsf {P} |_{O^{\mathsf {A} }\ne O^{\mathsf {B} }}$$. Typically, this distance is measured in statistical distance, or, in the computational setting, in computational indistinguishability. For this choice, Wullschleger [TCC ’09] showed that if $$\epsilon \ll \alpha $$ then the protocol can be transformed into an OT protocol.We consider measuring the protocol leakage by the log-ratio distance (which was popularized by its use in the differential privacy framework). The log-ratio distance between X, Y over domain $$\varOmega $$ is the minimal $$\epsilon \ge 0$$ for which, for every $$v \in \varOmega $$, $$\log \frac{\Pr [X=v]}{\Pr [Y=v]} \in [-\epsilon ,\epsilon ]$$. In the computational setting, we use computational indistinguishability from having log-ratio distance $$\epsilon $$. We show that a protocol with (noticeable) accuracy $$\alpha \in \varOmega (\epsilon ^2)$$ can be transformed into an OT protocol (note that this allows $$\epsilon \gg \alpha $$). We complete the picture, in this respect, showing that a protocol with $$\alpha \in o(\epsilon ^2)$$ does not necessarily imply OT. Our results hold for both the information theoretic and the computational settings, and can be viewed as a “fine grained” approach to “weak OT amplification”.We then use the above result to fully characterize the complexity of differentially private two-party computation for the XOR function, answering the open question put by Goyal, Khurana, Mironov, Pandey, and Sahai, [ICALP ’16] and Haitner, Nissim, Omri, Shaltiel, and Silbak [22] [FOCS ’18]. Specifically, we show that for any (noticeable) $$\alpha \in \varOmega (\epsilon ^2)$$, a two-party protocol that computes the XOR function with $$\alpha $$-accuracy and $$\epsilon $$-differential privacy can be transformed into an OT protocol. This improves upon Goyal et al. that only handle $$\alpha \in \varOmega (\epsilon )$$, and upon Haitner et al. who showed that such a protocol implies (infinitely-often) key agreement (and not OT). Our characterization is tight since OT does not follow from protocols in which $$\alpha \in o( \epsilon ^2)$$, and extends to functions (over many bits) that “contain” an “embedded copy” of the XOR function.