(Almost) Optimal Constructions of UOWHFs from 1-to-1, Regular One-way Functions and Beyond

Yu Yu, Dawu Gu, Xiangxue Li, and Jian Weng

Abstract

We revisit the problem of black-box constructions of universal one-way hash functions (UOWHFs) from several (from specific to more general) classes of one-way functions (OWFs), and give respective constructions that either improve or generalize the best previously known. In addition, the parameters we achieve are either optimal or almost optimal simultaneously up to small factors, e.g., arbitrarily small $\omega(1)$. For any 1-to-1 one-way function, we give an optimal construction of UOWHFs with key and output length $\Theta(n)$ by making a single call to the underlying OWF. This improves the constructions of Naor and Yung (STOC 1989) and De Santis and Yung (Eurocrypt 1990) that need key length $O(n*\omega(log n))$. For any known-(almost-)regular one-way function with known hardness, we give an optimal construction of UOWHFs with key and output length $\Theta(n)$ and a single call to the one-way function. For any known-(almost-)regular one-way function, we give a construction of UOWHFs with key and output length $O(n*\omega(1))$ and by making $\omega(1)$ non-adaptive calls to the one-way function. This improves the construction of Barhum and Maurer (Latincrypt 2012) that requires key and output length $O(n*\omega(log n))$ and $\omega(log n)$ calls. For any weakly-regular one-way function introduced by Yu et al. at TCC 2015 (i.e., the set of inputs with maximal number of siblings is of an $n^{-c}$-fraction for some constant $c$), we give a construction of UOWHFs with key length $O(n*log n)$ and output length $\Theta(n)$. This generalizes the construction of Ames et al. (Asiacrypt 2012) which requires an unknown-regular one-way function (i.e., $c=0$). Along the way, we use several techniques that might be of independent interest. We show that almost 1-to-1 (except for a negligible fraction) one-way functions and known (almost-)regular one-way functions are equivalent in the known-hardness (or non-uniform) setting, by giving an optimal construction of the former from the latter. In addition, we show how to transform any one-way function that is far from regular (but only weakly regular on a noticeable fraction of domain) into an almost-regular one-way function.

Available format(s)
Publication info
A major revision of an IACR publication in CRYPTO 2015
Keywords
FoundationsUniversal One-way Hash FunctionsOne-way functionsRandomized Iterate
Contact author(s)
yuyuathk @ gmail com
History
2015-06-10: last of 9 revisions
See all versions
Short URL
https://ia.cr/2014/393

CC BY

BibTeX

@misc{cryptoeprint:2014/393,
author = {Yu Yu and Dawu Gu and Xiangxue Li and Jian Weng},
title = {(Almost) Optimal Constructions of UOWHFs from 1-to-1, Regular One-way Functions and Beyond},
howpublished = {Cryptology ePrint Archive, Paper 2014/393},
year = {2014},
note = {\url{https://eprint.iacr.org/2014/393}},
url = {https://eprint.iacr.org/2014/393}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.