Paper 2022/431 Original: eprint.iacr.org/2022/431 ↗
Non-Adaptive Universal One-Way Hash Functions from Arbitrary One-Way Functions
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.
- History
- 2023-02-28: last updated
- 2022-04-06: published
- Short URL
- https://ia.cr/2022/431
- License
- https://creativecommons.org/licenses/by/4.0/
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}
}