Cryptology ePrint Archive: Report 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.

Category / Keywords: Foundations, Universal One-way Hash Functions, One-way functions, Randomized Iterate

Date: received 29 May 2014, last revised 3 Oct 2014

Contact author: yuyuathk at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20141003:103252 (All versions of this report)

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]