Paper 2014/393
(Almost) Optimal Constructions of UOWHFs from 1to1, Regular Oneway Functions and Beyond
Yu Yu, Dawu Gu, Xiangxue Li, and Jian Weng
Abstract
We revisit the problem of blackbox constructions of universal oneway hash functions (UOWHFs) from several (from specific to more general) classes of oneway 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 1to1 oneway 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 oneway function with known hardness, we give an optimal construction of UOWHFs with key and output length $\Theta(n)$ and a single call to the oneway function. For any known(almost)regular oneway function, we give a construction of UOWHFs with key and output length $O(n*\omega(1))$ and by making $\omega(1)$ nonadaptive calls to the oneway 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 weaklyregular oneway 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 unknownregular oneway function (i.e., $c=0$). Along the way, we use several techniques that might be of independent interest. We show that almost 1to1 (except for a negligible fraction) oneway functions and known (almost)regular oneway functions are equivalent in the knownhardness (or nonuniform) setting, by giving an optimal construction of the former from the latter. In addition, we show how to transform any oneway function that is far from regular (but only weakly regular on a noticeable fraction of domain) into an almostregular oneway function.
Metadata
 Available format(s)
 Publication info
 A major revision of an IACR publication in CRYPTO 2015
 Keywords
 FoundationsUniversal Oneway Hash FunctionsOneway functionsRandomized Iterate
 Contact author(s)
 yuyuathk @ gmail com
 History
 20150610: last of 9 revisions
 20140530: received
 See all versions
 Short URL
 https://ia.cr/2014/393
 License

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 1to1, Regular Oneway 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} }