Paper 2022/431

Non-Adaptive Universal One-Way Hash Functions from Arbitrary One-Way Functions

Xinyu Mao, Noam Mazor, and Jiapeng Zhang


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 Zheng [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.

Available format(s)
Publication info
Preprint. MINOR revision.
universal one-way hash functionsone-way functionnon-adaptive
Contact author(s)
xinyumao tcs @ gmail com
noammaz @ gmail com
jiapengz @ usc edu
2022-04-06: received
Short URL
Creative Commons Attribution


      author = {Xinyu Mao and Noam Mazor and Jiapeng Zhang},
      title = {Non-Adaptive Universal One-Way Hash Functions from Arbitrary One-Way Functions},
      howpublished = {Cryptology ePrint Archive, Paper 2022/431},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.