Paper 2014/393

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

Yu Yu and Dawu Gu and Xiangxue Li and Jian Weng

Abstract

A universal one-way hash function (UOWHF) is a compressing function for which finding a second preimage is infeasible. The seminal work of Rompel (STOC 1990) that one-way functions (OWFs) imply UOWHFs is one of the most important founding results of modern cryptography. The current best known UOWHF construction from any one-way function(on $n$-bit input) by Haitner et al. (Eurocrypt 2010) requires output and key length $\tilO(n^7)$, which is far from practical. On the other hand, special structured OWFs typically give rise to much more efficient (and almost practical) UOWHFs. Naor and Yung (STOC 1989) gave an optimal construction of UOWHFs of key and output lengths both linear in $n$ by making a single call to any one-way permutation. De Santis and Yung (Eurocrypt 1990), Barhum and Maurer (Latincrypt 2012), and Ames, Gennaro, and Venkitasubramaniam (Asiacrypt 2012) further extended the work to more generalized settings, namely, 1-to-1 and regular one-way functions. However, the best known constructions still require key length $O(n\cdot\log{n})$ even for 1-to-1 one-way functions, and need to make $O(\omega(1 {\cdot}\log{n})$ calls to any known regular one-way functions, or even $\tilO(n)$ adaptive calls if one wants linear output length at the same time. In this paper, we first introduce a technical lemma about universal hashing with nice symmetry to the leftover hash lemma, which might be of independent interest. That is, if one applies universal hash function $h:\bit{n}\rightarrow\bit{a+d}$ to any random variable $X$ of min-entropy $a$, then $h$ will be 1-to-1 on $X$ except for a $2^{-d}$ fraction. We also generalize the construction of Naor and Yung (that was optimal only for one-way permutations) to 1-to-1 and almost regular one-way functions, and significantly extend their analysis. The above yields the following results. \begin{itemize} \item 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. \item 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. \item For any known-(almost-)regular one-way function, we give a construction of UOWHFs with key and output length $O(\omega(1){\cdot}n)$ and by making $\omega(1)$ non-adaptive calls to the one-way function. \end{itemize} where the first two constructions enjoy optimal parameters simultaneously and the third one is nearly optimal up to any(efficiently computable) super-constant factor $\omega(1)$, e.g., $\log\log\log{n}$ or even less. Furthermore, the constructions enjoy optimal shrinkages by matching the upper bound of Gennaro et al. (SICOMP 2005).