Abstract
In this work we give the first non-adaptive construction of universal one-way hash functions (UOWHFs) from arbitrary one-way functions. Our construction uses \(O(n^9)\) calls to the one-way function, has a key of length \(O(n^{10})\), and can be implemented in NC1 assuming the underlying one-way function is in NC1.
Prior to this work, the best UOWHF construction used \(O(n^{13})\) adaptive calls and a key of size \(O(n^5)\) (Haitner, Holenstein, Reingold, Vadhan and Wee [Eurocrypt ’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, Reingold and Vadhan (HRV, [STOC ’10]), with small modifications, yields a relaxed notion of UOWHFs, which is a function family which can be (inefficiently) converted to UOWHF by changing the functions on a negligible fraction of the inputs. In order to analyze this construction, we introduce the notion of next-bit unreachable entropy, which replaces the next-bit pseudoentropy notion used by HRV.
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.
f is called regular if for every n and \(x,x'\) with \(\left| x\right| = \left| x'\right| =n\) it holds that \(\left| f^{-1}(f(x))\right| = \left| f^{-1}(f(x'))\right| \). We say that the function is unknown-regular if the regularity parameter, \(\left| f^{-1}(f(x))\right| \), may not be a computable function of n.
- 2.
The result of Applebaum, Ishai and Kushilevitz [4] implies that, using a method called randomized encoding, the existence of UOWHF in NC1 implies the existence of UOWHF in NC0.
- 3.
We use the term accessible entropy to denote accessible entropy of functions. Somewhat different notions of accessible entropy are used in other contexts, for example to construct statistically-hiding commitments from one-way functions [18].
- 4.
The actual definition of inaccessible entropy ignores some events that have a negligible probability.
- 5.
MZ actually show it is enough to use a single hash function. The number of repetitions n is necessary only to make the function shrinking.
- 6.
That is, \(g(X)_I\) is indistinguishable from some random variable Z (jointly distributed with X and I), such that \(H(Z\mid g(X)_{<I}) \ge k/\ell \). Here, \(H(Z\mid g(X)_{<I})\) is the conditional Shannon entropy of Z given \(g(X)_{<I}\) (see Sect. 3.5).
- 7.
If the function g is not injective, it is natural to consider \(g'(x)=(g(x),x)\). We use a similar construction in Sect. 5.
- 8.
Indeed, observe that \(H(g(X)_i\mid g(X)_{<i}=g(x)_{<i})\) is zero iff \(x\in \mathcal{U}_i\). Additionally, \(H(g(X)_i\mid g(X)_{<i}=g(x)_{<i})\le 1\) for every x. It follows that \(H(g(X)_i\mid g(X)_{<i})={\textbf{E}}_{x\leftarrow \left\{ 0,1\right\} ^m}\left[ H(g(X)_i\mid g(X)_{<i}=g(x)_{<i})\right] \le {\textbf{E}}_{x\leftarrow \left\{ 0,1\right\} ^m}\left[ 1_{x\notin \mathcal{U}_i}\right] = \textbf{Pr}\left[ X\notin \mathcal{U}_i\right] \).
- 9.
We use the term “reachable entropy” to denote the difference between the real entropy and the next-bit unreachable entropy of g(X).
- 10.
- 11.
Furthermore, the hybrid argument yields that \(w'\) must be from a small set if the collision for \(\widehat{\sigma }\) is.
- 12.
Actually, the proof in [15] only requires two-wise independence.
References
Agrawal, R., Chen, Y.-H., Horel, T., Vadhan, S.: Unifying computational entropies via Kullback–Leibler divergence. In: Boldyreva, A., Micciancio, D. (eds.) CRYPTO 2019. LNCS, vol. 11693, pp. 831–858. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-26951-7_28
Ames, S., Gennaro, R., Venkitasubramaniam, M.: The generalized randomized iterate and its application to new efficient constructions of UOWHFs from regular one-way functions. In: Wang, X., Sako, K. (eds.) ASIACRYPT 2012. LNCS, vol. 7658, pp. 154–171. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-34961-4_11
Applebaum, B., Haramaty-Krasne, N., Ishai, Y., Kushilevitz, E., Vaikuntanathan, V.: Low-complexity cryptographic hash functions. In: 8th Innovations in Theoretical Computer Science Conference, ITCS 2017. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2017). https://doi.org/10.4230/LIPIcs.ITCS.2017.7
Applebaum, B., Ishai, Y., Kushilevitz, E.: Cryptography in \(\text{ NC}^0\). SIAM J. Comput. 36(4), 845–888 (2006). https://doi.org/10.1137/S0097539705446950
Applebaum, B., Moses, Y.: Locally computable UOWHF with linear shrinkage. J. Cryptol. 30(3), 672–698 (2016). https://doi.org/10.1007/s00145-016-9232-x
Asharov, G., Segev, G.: Limits on the power of indistinguishability obfuscation and functional encryption. SIAM J. Comput. 45(6), 2117–2176 (2016). https://doi.org/10.1137/15M1034064
Barhum, K., Holenstein, T.: A cookbook for black-box separations and a recipe for UOWHFs. In: Sahai, A. (ed.) TCC 2013. LNCS, vol. 7785, pp. 662–679. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-36594-2_37
Barhum, K., Maurer, U.: UOWHFs from OWFs: trading regularity for efficiency. In: Hevia, A., Neven, G. (eds.) LATINCRYPT 2012. LNCS, vol. 7533, pp. 234–253. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-33481-8_13
Berman, I., Degwekar, A., Rothblum, R.D., Vasudevan, P.N.: Multi-collision resistant hash functions and their applications. In: Nielsen, J.B., Rijmen, V. (eds.) EUROCRYPT 2018. LNCS, vol. 10821, pp. 133–161. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-78375-8_5
Bitansky, N., Kalai, Y.T., Paneth, O.: Multi-collision resistance: a paradigm for keyless hash functions. In: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pp. 671–684 (2018). https://doi.org/10.1145/3188745.3188870
Blum, M., Micali, S.: How to generate cryptographically strong sequences of pseudo random bits. In: Annual Symposium on Foundations of Computer Science (FOCS), pp. 112–117 (1982). https://doi.org/10.1109/SFCS.1982.72
Gennaro, R., Gertner, Y., Katz, J., Trevisan, L.: Bounds on the efficiency of generic cryptographic constructions. SIAM J. Comput. 35(1), 217–246 (2005). https://doi.org/10.1137/S0097539704443276
Goldreich, O.: Candidate one-way functions based on expander graphs. In: Goldreich, O. (ed.) Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation. LNCS, vol. 6650, pp. 76–87. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-22670-0_10
Haitner, I., Harnik, D., Reingold, O.: On the power of the randomized iterate. In: Dwork, C. (ed.) CRYPTO 2006. LNCS, vol. 4117, pp. 22–40. Springer, Heidelberg (2006). https://doi.org/10.1007/11818175_2
Haitner, I., Holenstein, T., Reingold, O., Vadhan, S., Wee, H.: Universal one-way hash functions via inaccessible entropy. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol. 6110, pp. 616–637. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-13190-5_31
Haitner, I., Mazor, N., Silbak, J.: Incompressibility and next-block pseudoentropy. 14th Innovations in Theoretical Computer Science (2023)
Haitner, I., Reingold, O., Vadhan, S.: Efficiency improvements in constructing pseudorandom generators from one-way functions. SIAM J. Comput. 42(3), 1405–1430 (2013). https://doi.org/10.1137/100814421
Haitner, I., Reingold, O., Vadhan, S., Wee, H.: Inaccessible entropy. In: Proceedings of the 41st Annual ACM Symposium on Theory of Computing, pp. 611–620 (2009). https://doi.org/10.1145/1536414.1536497
Håstad, J., Impagliazzo, R., Levin, L.A., Luby, M.: A pseudorandom generator from any one-way function. SIAM J. Comput. 28(4), 1364–1396 (1999). https://doi.org/10.1137/S0097539793244708
Holenstein, T., Sinha, M.: Constructing a pseudorandom generator requires an almost linear number of calls. In: 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science, pp. 698–707. IEEE (2012). https://doi.org/10.1109/FOCS.2012.51
Holmgren, J., Lombardi, A.: Cryptographic hashing from strong one-way functions (or: one-way product functions and their applications). In: 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pp. 850–858. IEEE (2018). https://doi.org/10.1109/FOCS.2018.00085
Katz, J., Koo, C.Y.: On constructing universal one-way hash functions from arbitrary one-way functions. Cryptology ePrint Archive (2005)
Komargodski, I., Naor, M., Yogev, E.: Collision resistant hashing for paranoids: dealing with multiple collisions. In: Nielsen, J.B., Rijmen, V. (eds.) EUROCRYPT 2018. LNCS, vol. 10821, pp. 162–194. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-78375-8_6
Mao, X., Mazor, N., Zhang, J.: Non-adaptive universal one-way hash functions from arbitrary one-way functions. Cryptology ePrint Archive, Paper 2022/431 (2022). https://eprint.iacr.org/2022/431
Mazor, N., Zhang, J.: Simple constructions from (almost) regular one-way functions. In: Nissim, K., Waters, B. (eds.) TCC 2021. LNCS, vol. 13043, pp. 457–485. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-90453-1_16
Naor, M., Yung, M.: Universal one-way hash functions and their cryptographic applications. In: Proceedings of the 21st Annual ACM Symposium on Theory of Computing, pp. 33–43 (1989). https://doi.org/10.1145/73007.73011
Rompel, J.: One-way functions are necessary and sufficient for secure signatures. In: Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, pp. 387–394 (1990). https://doi.org/10.1145/100216.100269
Rothblum, R.D., Vasudevan, P.N.: Collision-resistance from multi-collision-resistance. In: Advances in Cryptology-CRYPTO 2022: 42nd Annual International Cryptology Conference, CRYPTO 2022, Santa Barbara, CA, USA, 15–18 August 2022, Proceedings, Part III, pp. 503–529. Springer, Heidelberg (2022). https://doi.org/10.1007/978-3-031-15982-4_17
Vadhan, S., Zheng, C.J.: Characterizing pseudoentropy and simplifying pseudorandom generator constructions. In: Proceedings of the 44th Annual ACM Symposium on Theory of Computing, pp. 817–836 (2012). https://doi.org/10.1145/2213977.2214051
Yao, A.C.: Theory and application of trapdoor functions. In: 23rd Annual Symposium on Foundations of Computer Science, SFCS 1982, pp. 80–91. IEEE (1982). https://doi.org/10.1109/SFCS.1982.45
Yu, Yu., Gu, D., Li, X., Weng, J.: (Almost) optimal constructions of UOWHFs from 1-to-1, regular one-way functions and beyond. In: Gennaro, R., Robshaw, M. (eds.) CRYPTO 2015. LNCS, vol. 9216, pp. 209–229. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-48000-7_11
Acknowledgments
We are very thankful to Iftach Haitner for very useful discussions, and to the anonymous referees for valuable comments and their significant help with improving the presentation of this work.
The research of X. Mao and J. Zhang is supported by NSF CAREER award 2141536. The research of N. Mazor is supported by Israel Science Foundation grant 666/19.
Author information
Authors and Affiliations
Corresponding authors
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2023 International Association for Cryptologic Research
About this paper
Cite this paper
Mao, X., Mazor, N., Zhang, J. (2023). Non-adaptive Universal One-Way Hash Functions from Arbitrary One-Way Functions. In: Hazay, C., Stam, M. (eds) Advances in Cryptology – EUROCRYPT 2023. EUROCRYPT 2023. Lecture Notes in Computer Science, vol 14007. Springer, Cham. https://doi.org/10.1007/978-3-031-30634-1_17
Download citation
DOI: https://doi.org/10.1007/978-3-031-30634-1_17
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-30633-4
Online ISBN: 978-3-031-30634-1
eBook Packages: Computer ScienceComputer Science (R0)
