International Association
for Cryptologic Research

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.