Paper 2022/431

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

Xinyu Mao, University of Southern California
Noam Mazor, Tel Aviv University
Jiapeng Zhang, University of Southern California
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(n13) adaptive calls and a key of size O(n5) (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.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint.
Keywords
universal one-way hash functionsone-way functionnon-adaptive
Contact author(s)
xinyumao tcs @ gmail com
noammaz @ gmail com
jiapengz @ usc edu
History
2023-02-28: revised
2022-04-06: received
See all versions
Short URL
https://ia.cr/2022/431
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/431,
      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},
      url = {https://eprint.iacr.org/2022/431}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.