Abstract
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). 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.
A. Beimel—Part of this work was done while visiting the Simons Institute. Research partly supported by ISF grant 391/21.
T. Malkin—Part of this work was done while visiting the Simons Institute. Research supported by NSF CCF-2312242 and an Amazon Research Award.
N. Mazor—Part of this work was done while at Cornell Tech and while visiting the Simons Institute. Research partly supported by NSF CNS-2149305.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
- 2.
Their paper, and its journal version [MV15], has other results as well, in particular about increasing PRG stretch in a black box way; we focus here on the result relevant to our paper.
- 3.
Here \(x_{\le i}\) denotes the first i bits of x.
- 4.
In the actual proof we show how to do it for outputs of length \(n-\omega (\log n)\).
- 5.
- 6.
Actually, \(n/2+\omega (\log n)\), but we ignore it for this presentation.
- 7.
This is already enough to get some lower bound. As Tianqi Yang commented to us, if we assume that the PRF construction is secure even when using different PRG in each one of the levels, we can construct each one of the functions \(\tau _i\) by applying the pseudo-inverse lemma separately for each \(S_i\). Specifically, letting \(\pi _i\) be the pseudo-inverse of \(S_i\), and taking the PRG \(G_i\) to be \(\pi _i\circ G\), we can get that \(S_t(G_t(S_{t-1}(G_{t-1}(\dots S_0(k,x)\dots ))))=\widehat{f}(k,x)\) for some function \(\widehat{f}\) (and for any \(t\in o(n/\log n))\). Interestingly, the GGM construction has this type of security.
References
Applebaum, B., Raykov, P.: Fast pseudorandom functions based on expander graphs. In: Hirt, M., Smith, A. (eds.) TCC 2016. LNCS, vol. 9985, pp. 27–56. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53641-4_2
Boneh, D., Montgomery, H.W., Raghunathan, A.: Algebraic pseudorandom functions with improved efficiency from the augmented cascade. In: Proceedings of the 17th ACM Conference on Computer and Communications Security, pp. 131–140 (2010)
Banerjee, A., Peikert, C., Rosen, A.: Pseudorandom functions and lattices. In: Pointcheval, D., Johansson, T. (eds.) EUROCRYPT 2012. LNCS, vol. 7237, pp. 719–737. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-29011-4_42
Gennaro, R., Gertner, Y., Katz, J., Trevisan, L.: Bounds on the efficiency of generic cryptographic constructions. SIAM J. Comput. 35(1), 217–246 (2005)
Goldreich, O., Goldwasser, S., Micali, S.: How to construct random functions. J. ACM (JACM) 33(4), 792–807 (1986)
Gertner, Y., Malkin, T., Reingold, O.: On the impossibility of basing trapdoor functions on trapdoor predicates. In: Proceedings 42nd IEEE Symposium on Foundations of Computer Science, pp. 126–135. IEEE (2001)
Haitner, I., Hoch, J.J., Reingold, O., Segev, G.: Finding collisions in interactive protocols-a tight lower bound on the round complexity of statistically-hiding commitments. In: 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS’07), pp. 669–679. IEEE (2007)
Impagliazzo, R.: Relativized separations of worst-case and averagecase complexities for NP. In: 2011 IEEE 26th Annual Conference on Computational Complexity, pp. 104–114. IEEE (2011)
Levin, L.A.: One way functions and pseudorandom generators. Combinatorica 7(4), 357–363 (1987)
Linial, N., Mansour, Y., Nisan, N.: Constant depth circuits, Fourier transform, and learnability. J. ACM (JACM) 40(3), 607–620 (1993)
Lewko, A.B., Waters, B.: Efficient pseudorandom functions from the decisional linear assumption and weaker variants. In: Proceedings of the 16th ACM Conference on Computer and Communications Security, pp. 112–120 (2009)
Miles, E., Viola, E.: On the complexity of non-adaptively increasing the stretch of pseudorandom generators. In: Ishai, Y. (ed.) TCC 2011. LNCS, vol. 6597, pp. 522–539. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-19571-6_31
Miles, E., Viola, E.: On the complexity of constructing pseudorandom functions (especially when they don’t exist). J. Cryptol. 28(3), 509–532 (2015)
Naor, M., Reingold, O.: Number-theoretic constructions of efficient pseudo-random functions. J. ACM (JACM) 51(2), 231–262 (2004)
Naor, M., Reingold, O.: Synthesizers and their application to the parallel construction of pseudo-random functions. J. Comput. Syst. Sci. 58(2), 336–375 (1999)
Naor, M., Reingold, O., Rosen, A.: Pseudo-random functions and factoring. In: Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, pp. 11–20 (2000)
Nisan, N., Wigderson, A.: Hardness vs randomness. J. Comput. Syst. Sci. 49(2), 149–167 (1994)
Pitt, L., Warmuth, M.K.: Reductions among prediction problems: on the difficulty of predicting automata. In: 1988 Structure in Complexity Theory Third Annual Conference, pp. 60–61. IEEE Computer Society (1988)
Razborov, A.A., Rudich, S.: Natural proofs. In: Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, pp. 204–213 (1994)
Reingold, O., Trevisan, L., Vadhan, S.: Notions of reducibility between cryptographic primitives. In: Naor, M. (ed.) TCC 2004. LNCS, vol. 2951, pp. 1–20. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-24638-1_1
Vadhan, S.P., et al.: Pseudorandomness. Found. Trends® Theor. Comput. Sci. 7(1–3), 1–336 (2012)
Valiant, L.G.: A theory of the learnable. Commun. ACM 27(11), 1134–1142 (1984)
Acknowledgment
We thank Yanyi Liu, Tamer Mour, and Tianqi Yang for very useful discussions.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2024 International Association for Cryptologic Research
About this paper
Cite this paper
Beimel, A., Malkin, T., Mazor, N. (2024). Structural Lower Bounds on Black-Box Constructions of Pseudorandom Functions. In: Reyzin, L., Stebila, D. (eds) Advances in Cryptology – CRYPTO 2024. CRYPTO 2024. Lecture Notes in Computer Science, vol 14924. Springer, Cham. https://doi.org/10.1007/978-3-031-68388-6_16
Download citation
DOI: https://doi.org/10.1007/978-3-031-68388-6_16
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-68387-9
Online ISBN: 978-3-031-68388-6
eBook Packages: Computer ScienceComputer Science (R0)
