You are looking at a specific version 20141003:103252 of this paper. See the latest version.

Paper 2014/393

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

Yu Yu and Dawu Gu and 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 constructions accordingly that either improve the best previously known or generalize to a broader class of one-way functions. In addition, the parameters we achieve are either optimal or almost optimal simultaneously up to small factors, e.g., $O(\log{n})$ or arbitrarily small $\omega(1)$. For any 1-to-1 one-way function (and not necessarily a one-way permutation), 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 another 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 one-way function $f$ that is weakly unknown-regular (i.e., the set of $x$'s 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 introduce several technical tools and techniques that might be of independent interest. The first tool is a technical lemma about universal hashing with nice symmetry to the leftover hash lemma. Secondly, 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. Thirdly, 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 unknown-almost-regular one-way function.

Metadata
Available format(s)
PDF
Publication info
Preprint. MINOR revision.
Keywords
FoundationsUniversal One-way Hash FunctionsOne-way functionsRandomized Iterate
Contact author(s)
yuyuathk @ gmail com
History
2015-06-10: last of 9 revisions
2014-05-30: received
See all versions
Short URL
https://ia.cr/2014/393
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.