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

Abstract

We revisit the problem of black-box constructions of universal one-way hash functions (UOWHFs) from several typical classes of one-way functions (OWFs), and give respective constructions that either improve or generalize the best previously known.

• For any 1-to-1 one-way function, we give an optimal construction of UOWHFs with key and output length $\varTheta (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\cdot \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 $\varTheta (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{\cdot }\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{\cdot }\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{\cdot }{\log }n)$ and output length $\varTheta (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.

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

1 Introduction

Informally, a family of compressing hash functions, denoted by $\mathcal {G}$, is called universal one-way, if given a random function $g\in \mathcal {G}$ and a random (or equivalently, any pre-fixed) input x, it is infeasible for any efficient algorithm to find any $x'\ne {x}$ satisfying $g(x)=g(x')$. The seminal result that one-way functions (OWFs) imply universal one-way hash functions (UOWHFs) [17] constitutes one of the central pieces of modern cryptography. Applications of UOWHFs include basing digital signatures [9] on minimal assumptions (one-way functions), Cramer-Shoup encryption scheme [4], statistically hiding commitment scheme [12, 13], etc.

UOWHFs from any OWFs. The principle possibility result that UOWHFs can be based on any OWF was established by Rompel [17] (with some corrections given in [15, 18]). However, Rompel’s construction was quite complicated and extremely unpractical. In particular, for any one-way function on n-bit inputs it requires key length $\tilde{O}(n^{12})$ and output length $\tilde{O}(n^{8})$. Haitner et al. [11] improved the construction via the notion of inaccessible entropy [13], and reduced key and output length to $\tilde{O}(n^{7})$. Therefore, even the best known generic UOWHF constructions (based on arbitrary OWFs) are mainly of theoretical interest and are too inefficient to be of any practical use.

UOWHFs from special OWFs. Another line of research focuses on more efficient (and nearly practical) constructions of UOWHFs from special structured OWFs. Naor and Yung gave an elegant “hash-then-truncate” construction of UOWHFs with key and output length $\varTheta (n)$ which does a single call to any one-way permutation. However, for a slightly weaker primitive, namely, 1-to-1 one-way functions, the authors of [16] only gave a rather complicated construction. De Santis and Yung [19] gave an improved construction from any 1-to-1 OWF $f: \{0, 1\}^{n} \rightarrow \{0, 1\}^{l}$ as below:

where “$\circ$” denotes function composition, each $\mathcal {H}_{i-1}^{i}$ denotes a family of pairwise-independent hash functions that compress i-bit strings into $(i-1)$ bits. Although $\mathcal {G}_{1-1}$ enjoys linear output length and a single function call, it requires¹ key length $O(\omega (\log {n}){\cdot }n)$. In addition, the work of [19] also introduced a construction from any known-regular² one-way function with key and output length $O(\omega (\log ^2{n})\cdot {n})$ and $O(\omega (1)\cdot \log {n})$ adaptive calls, which was recently improved by Barhum and Maurer [3] to key and output length $O(\omega (\log {n})\cdot {n})$ and $O(\omega (1)\cdot \log {n})$ non-adaptive calls. Based on unknown-regular one-way functions, Ames et al. [1] presented a more general construction with output length $\varTheta (n)$, key length $O({\log }n\cdot {n})$ and $\tilde{O}(n)$ adaptive calls. We refer to Table 1 for a summary of previous constructions and a comparison to our work.

Table 1. A summary of existing constructions [1, 3, 16, 19] and our work, where KR-OWF and UR-OWF are the shorthands for known-regular and unknown-regular one-way functions respectively, $\varepsilon$-hard KR-OWF additionally assumes that the hardness parameter $\varepsilon$ of KR-OWF is known, and $n^{-c}$-WUR-OWF is the shorthand for weakly unknown-regular one-way functions (see Footnote 7 and formally Definition 9).

Summary of our constructions. In this paper, we give the following constructions from the respective aforementioned one-way functions. The first two constructions enjoy optimal parameters simultaneously and they are (almost) security-preserving³, the third achieves parameters that are almost optimal up to an arbitrarily small super-constant factor $\omega (1)$ (e.g., $\log \log \log {n}$ or even less), and thus they all improve upon the respective known constructions. The fourth construction generalizes to beyond regular one-way functions (as introduced in [21]) with optimal output length $\varTheta (n)$ and key length $O(n\cdot \log {n})$.

• 1. For any 1-to-1 one-way function, we construct an optimal family of UOWHFs with key and output length $\varTheta (n)$ and a single OWF call.

• 2. For any known-regular one-way function with known hardness, we give another optimal construction of UOWHFs with key and output length $\varTheta (n)$ and a single call.

• 3. For any known-regular one-way function, we give a construction of UOWHFs with key and output length $O(\omega (1){\cdot }n)$ and $\omega (1)$ non-adaptive calls.

• 4. For any one-way function f that is weakly unknown-regular on a noticeable fraction (i.e., $n^{-c}$ for constant c) of domain [21], we give a construction of UOWHFs with key length $O(n{\cdot }{\log }n)$ and output length $\varTheta (n)$.

On the (a)symmetry to PRGs. Our results further exhibit the inherent “black-box duality” [5, 11, 13] between UOWHFs and PRGs. Firstly, we abstract out a lemma about universal hashing (see Lemma 1) that is implicit in previous works [13, 15, 17] and plays a dual role in UOWHF constructions to the leftover hash lemma in PRG constructions. Secondly, constructions #2 and #3 above match the best known results about constructions of PRGs from known-regular OWFs (see [22]), namely, seed length $O(\omega (1){\cdot }n)$ or even $\varTheta (n)$ if the hardness of the underlying OWF is known. Thirdly, construction #4 is symmetric to the recent PRG construction [21] based on the same class of one-way functions with succinct key/seed length $O(n\cdot \log {n})$. Finally (and perhaps more interestingly), construction #1 is asymmetric to the case of PRGs, where we do not know how to construct a linear seed length PRG from an arbitrary 1-to-1 one-way function⁴.

On the efficiency, feasibility and limits. Constructions #1, #2 and #3 are practically relevant as most one-way function candidates turn out to be known-almost-regular or even 1-to-1. Goldreich, Levin and Nisan [8] showed how to base almost 1-to-1 (except for a negligible fraction) one-way functions on intractable problems such as RSA and DLP, and thus construction #1 enables to build optimal UOWHFs from those problems. A byproduct of construction #2 is the equivalence of almost 1-to-1 one-way functions and known-(almost-)regular one-way functions in certain (known-hardness or non-uniform) settings, where we give an optimal construction of the former from the latter. Moreover, unknown regular one-way functions further reduce the knowledge required about the underlying one-way functions, and the problem of basing cryptographic primitives (PRGs, UOWHFs, etc.) on weaker assumptions is of theoretic interests. It improves our understanding about the feasibility and limits of black-box reductions. In particular, Holenstein and Sinha [14], Barhum and Holenstein [2] showed that $\Omega (n/\log {n}$) black-box calls to an arbitrary (including unknown-regular) one-way function is necessary to construct PRGs and UOWHFs, and the lower bound is matched by explicit constructions of PRGs [10] and UOWHFs [1] respectively. The recent work of [21] carried on this line of research even further by considering a more general class of one-way functions (which they call weakly unknown-regular one-way functions), namely, the underlying one-way function can have an arbitrary structure as long as the set of x with maximal number of siblings (i.e., x and $x'$ are siblings of each other if $f(x)=f(x')$) is of noticeable fraction. The authors of [21] gave a construction of PRG with seed length $O(n\cdot \log {n})$ from weakly unknown-regular OWFs. However, their analysis is quite ad-hoc (see Remark 2), and doesn’t seem to generalize to UOWHFs. As an intermediate step of construction #4, we prove that “iterating such a one-way function (weakly regular on only a noticeable fraction) polynomially many times yields a one-way function that is almost-regular on an overwhelming fraction” and thus unify the approach to the two dual objects (i.e., PRGs and UOWHFs).

The roadmap. We outline below the steps to build UOWHFs from the respective one-way function $f: \{0, 1\}^{n} \rightarrow \{0, 1\}^{l}$ introduced above. We note that the following assumptions (about output length) can be made without loss of generality: $l\in {O(n)}$ for 1-to-1 one-way functions and length-preserving-ness (i.e., $l=n$) for arbitrary one-way functions. More specifically, any 1-to-1 one-way function $f: \{0, 1\}^{n} \rightarrow \{0, 1\}^{l}$ implies a one-way function $f': \{0, 1\}^{n'\in \varTheta (n)} \rightarrow \{0, 1\}^{l'\in \varTheta (n)}$ that is 1-to-1 except for a negligible fraction. Any one-way function f with $\alpha \le |f^{-1}(y)|\le \alpha {\cdot }\beta$ implies another length-preserving one-way function $f': \{0, 1\}^{n'\in \varTheta (n)} \rightarrow \{0, 1\}^{n'}$ with $\alpha '\le |f'^{-1}(y)|\le \alpha '{\cdot }\beta$ except for a negligible fraction, where the size of range $\beta$ is preserved, and $\alpha '$ is efficiently computable if $\alpha$ is. We refer to [20] for a full proof.

Based on 1-to-1 OWFs. We adapt Naor-Yung’s elegant “hash-then-truncate” approach (for one-way permutation) to any 1-to-1 one-way function:

where $\mathcal {H}$ is a family of universal hash permutations on l bits, and $\mathsf{trunc}: \{0, 1\}^{l} \rightarrow \{0, 1\}^{n-s}$ is a truncating function that outputs the first $n-s$ bits of input. We show that if f is a (t,$\varepsilon$)- 1-to-1 OWF then the resulting $\mathcal {G}_1$ is a ($t-n^{O(1)}$, $2^{s+1}\cdot \varepsilon$)-UOWHF family with key and output length $\varTheta (n)$ and shrinkage s (see Definitions 3 and 7 for formal definitions). The construction enjoys optimal parameters and somewhat counter-intuitively the security bound drops only by factor $2^s$ (which is optimal by [5]) rather than by $2^{l-n+s}$ (i.e., exponential in the number of bits truncated which would render the construction useless). We refer to the proof of Theorem 1 and Remark 1 for more technical details and further discussions.

Based on known-(almost-)regular $\varepsilon$ -hard OWFs. Given an almost-regular f (see Definition 6) which is known to be (t,$\varepsilon$)-one-way for some efficiently computable $\varepsilon$, we define the following function family

where $\mathcal {H}$ is a family of universal hash permutations, and let $\mathcal {H}_1$ and $\mathsf {trunc}$ be a family of universal hash functions and the truncating function (both with appropriate output sizes) respectively. We show that $\mathcal {G}_2$ is a UOWHF family with key and output length $\varTheta (n)$ and shrinkage s. The rationale is that for any⁵ $x\ne {x'}$ colliding on $g\in \mathcal {G}_2$ it either satisfies “$f(x)=f(x')~{\wedge }~h_1(x)=h_1(x')$” or “$f(x){\ne }f(x')~\wedge ~\mathsf{trunc}(h(f(x)))=\mathsf{trunc}(h(f(x')))$”. The former is unconditionally bounded by universal hashing, and the latter is computationally bounded (and reducible to the one-way-ness of f). Interestingly, by abstracting out function from the above construction, we further show that $f'$ is a one-way function that is 1-to-1 except for a negligible fraction. We refer to Theorem 2, Lemma 2 and Theorem 3 for the details.

Based on known-(almost-)regular OWFs. Next, we consider any known-(almost)-regular OWF f whose hardness parameter is $\varepsilon$ unknown (i.e., $\varepsilon$ is negligible but may not be efficiently computable). In this case, we run q independent copies of f, and we get a construction by making q non-adaptive calls with shrinkage $q\log {n}$, key and output length $O(q\cdot {n})$, where $q\in \omega (1)$ can be any efficiently computable super-constant. The parallel repetition technique was also used in similar contexts (e.g., the construction of PRG from any known regular OWF [22]). We refer to Theorem 4 for the detailed construction and proof.

Based on a more general class of OWFs. We show iterating the class of one-way functions introduced in [21] sufficiently many times yields a one-way function $f'$ that is almost-regular, and thus plugging this $f'$ into the construction of Ames et al. [1] yields a construction of UOWHFs with output length $\varTheta (n)$ and key length $O(n\cdot \log {n})$.

2 Preliminaries

Notations and definitions. We use [n] to denote set {1, ..., n}. We use capital letters (e.g., X, Y) for random variables, standard letters (e.g., x, y) for values, and calligraphic letters (e.g. $\mathcal {X}$, $\mathcal {Y}$) for sets. The support of a random variable X, denoted by Supp(X), refers to the set of values on which X takes with non-zero probability, i.e., $\{x:\Pr [X=x]>0\}$. For a binary string $x=x_1\ldots {x_n}$, denote by $x_{[t]}$ the first t bits of x, i.e., $x_1\ldots {x_t}$. $x\Vert y$ refers the concatenation of x and y. We denote by $\mathsf{trunc}: \{0, 1\}^{n} \rightarrow \{0, 1\}^{t}$ a truncating function that outputs the first t bits of input, i.e., $\mathsf{trunc}(x)=x_{[t]}$. $|\mathcal {S}|$ denotes the cardinality of set $\mathcal {S}$. For function $f: \{0, 1\}^{n} \rightarrow \{0, 1\}^{l(n)}$, we use shorthand , and denote by $f^{-1}(y)$ the set of y’s preimages under f, i.e., . We say f is length-preserving if $l(n)=n$. We use $s\leftarrow {S}$ to denote sampling an element s according to distribution S, and let $s\xleftarrow {\$}{\mathcal {S}}$ denote sampling s uniformly from set $\mathcal {S}$, and $y:=f(x)$ denote value assignment. We use $U_n$ and $U_{\mathcal {X}}$ to denote uniform distributions over $\{0, 1\}^{n}$ and $\mathcal {X}$ respectively, and let $f(U_n)$ be the distribution induced by applying function f to $U_n$. For probabilistic algorithm $\mathsf{A}$, we use $\mathsf{A}(x;r)$ to denote the output of $\mathsf{A}$ on input x and internal coin r. The min-entropy and max-entropy (see, e.g., [13]) of a random variable X, denoted by ${{\mathbf {H}}_{\infty }}(X)$ and ${{\mathbf {H}}_{0}}(X)$ respectively, are defined as:

We use ‘$+/-$’ and ‘$\cdot$’ for addition/subtraction and multiplication between field elements respectively. The zero element of any finite field is denoted by $\mathbf {0}$.

Collision probability. We use $\mathsf {CP}(X)$ to denote the collision probability of X, i.e., , and denote by $\mathsf {CP}(X|Z)$ the average collision probability of X conditioned on another (possibly correlated) random variable Z by

Simplifying Notations. Parameters (e.g., $\varepsilon$, r) are said to be known if they are polynomial-time computable from the security parameter n. By notation $f: \{0, 1\}^{n} \rightarrow \{0, 1\}^{l}$ we refer to the ensemble of functions $\{f: \{0, 1\}^{n} \rightarrow \{0, 1\}^{l(n)} \}_{n\in \mathbb {N}}$. As slight abuse of notion, $\mathsf {poly}$ might be referring to the set of all polynomials or a certain polynomial, and h might be either a function or its description which will be clear from context. For example, in the first h denotes a function, the second h refers to a string (a finite field element) that describes the function (i.e., multiplying y by h).

Definition 1

( $\varvec{\rho }$ -almost universal hashing). A family of functions $\mathcal {H}=\{h: \{0, 1\}^{l} \rightarrow \{0, 1\}^{t} \}$ is $\rho$-almost universal if for any distinct $x_1,{x_2}\in \{0, 1\}^{l}$, it holds that

$$\begin{aligned} \Pr _{h\xleftarrow {\$}\mathcal {H}}[h(x_1)=h(x_2)]\le \rho . \end{aligned}$$

In the special case $\rho =2^{-t}$, we say that $\mathcal {H}$ is universal.

Definition 2

(pairwise independent hashing). A family of functions $\mathcal {H}=\{h: \{0, 1\}^{l} \rightarrow \{0, 1\}^{t} \}$ is pairwise independent if any distinct $x_1,{x_2}\in \{0, 1\}^{l}$ and any $v_1,v_2\in \{0, 1\}^{t}$ it holds that $\Pr _{h\xleftarrow {\$}\mathcal {H}}[~h(x_1)=v_1~{\wedge }~h(x_2)=v_2~]=2^{-2t}$.

Definition 3

(one-way functions). A sequence of functions $\{f: \{0, 1\}^{n} \rightarrow \{0, 1\}^{l(n)} \}_{n\in \mathbb {N}}$ is (t(n),$\varepsilon (n)$)-one-way if f is polynomial-time computable and for any probabilistic algorithm $\mathsf{A}$ of running time t(n)

$$\begin{aligned} \Pr _{x\xleftarrow {\$} \{0, 1\}^{n} }[\mathsf{A}(1^n,f(x)){\in }f^{-1}(f(x))]~\le ~\varepsilon (n). \end{aligned}$$

Hereafter we use simplified notation $f: \{0, 1\}^{n} \rightarrow \{0, 1\}^{l(n)}$ for the above one-way function, where $t(\cdot )$ and $1/\varepsilon (\cdot )$ are super-polynomial.

Definition 4

(a family of one-way functions). A sequence of function family $\mathcal {F}=\{\mathcal {F}_n\}_{n{\in }\mathbb {N}}$, where $\mathcal {F}_n=\{f_u: \{0, 1\}^{n} \rightarrow \{0, 1\}^{l(n)} ,u\in \{0, 1\}^{q(n)} \}$, is (t(n),$\varepsilon (n)$)-one-way if for any $n\in \mathbb {N}$, $u\in \{0, 1\}^{q(n)}$ and $x\in \{0, 1\}^{n}$, the value $f_u(x)$ can be computed in polynomial time, and for any probabilistic algorithm $\mathsf{A}$ of running time t(n), we have that

We use shorthands $\mathcal {F}=\{f_u: \{0, 1\}^{n} \rightarrow \{0, 1\}^{l(n)} ,u\in \{0, 1\}^{q(n)} \}$ for $\{\mathcal {F}_n\}_{n{\in }\mathbb {N}}$.

Definition 5

(almost 1-to-1 functions). A function $f: \{0, 1\}^{n} \rightarrow \{0, 1\}^{l(n)}$ is $\varepsilon (n)$-almost 1-to-1 if there exists a negligible function $\varepsilon (n)$, such that for every $n\in \mathbb {N}$ we have

$$\begin{aligned} \Pr _{x\xleftarrow {\$} \{0, 1\}^{n} }[~\exists {x'}:~x'\ne {x}~{\wedge }~f(x)=f(x')~]\le \varepsilon (n). \end{aligned}$$

In particular, f is 1-to-1 if $\varepsilon (n)\equiv {0}$.

Definition 6

(almost regular functions). For integer functions $\alpha =\alpha (n)$ and $\beta =\beta (n)$, a function $f: \{0, 1\}^{n} \rightarrow \{0, 1\}^{l(n)}$ is $\alpha$-regular if for every $n\in \mathbb {N}$ and $x\in \{0, 1\}^{n}$ we have

$$\begin{aligned} |f^{-1}(f(x))|=\alpha . \end{aligned}$$

f is ($\alpha$, $\alpha {\cdot }\beta$)-almost regular if for every $n\in \mathbb {N}$ and $x\in \{0, 1\}^{n}$ we have

$$\begin{aligned} \alpha ~\le ~|f^{-1}(f(x))|~\le ~\alpha \cdot {\beta }. \end{aligned}$$

In particular, f is known-(almost)-regular if $\alpha$ is polynomial-time computable, or otherwise it is called unknown-(almost)-regular. Standard “almost-regularity” for a $(t,\varepsilon )$-one-way function f refers to that f is ($\alpha$, $\alpha {\cdot }\beta$)-almost-regular for $\beta ={\mathsf {poly}(n)}$ or at most $\beta ={(1/\varepsilon )^{\varTheta (1)}}$ for certain small constant $0<\varTheta (1)<1$.

Definition 7

(UOWHFs [16]). A sequence of function family $\mathcal {G}=\{\mathcal {G}_n\}_{n{\in }\mathbb {N}}$, where $\mathcal {G}_n=\{g_u: \{0, 1\}^{\ell (n)} \rightarrow \{0, 1\}^{\ell (n)-s(n)} , u\in \{0, 1\}^{q(n)} ,\ell \in \mathsf {poly}\}$, is a family of (t(n),$\varepsilon (n)$)-universal one-way hash functions if for every $n\in \mathbb {N}$, $u\in \{0, 1\}^{q(n)}$ and $x\in \{0, 1\}^{\ell (n)}$, the value $g_u(x)$ can be computed in polynomial time, and for every probabilistic algorithm $\mathsf{A}$ of running time t(n), it holds that

The difference between input and output lengths (i.e., s(n)) is called shrinkage. For succinctness, hereafter we will use shorthand $\mathcal {G}=\{g_u: \{0, 1\}^{\ell } \rightarrow \{0, 1\}^{\ell -s}$, $u\in \{0, 1\}^{q} \}$ for $\{\mathcal {G}_n\}_{n{\in }\mathbb {N}}$ defined above.

3 UOWHFs from 1-to-1 One-Way Functions

3.1 A Technical Lemma and Its Applications

We state below a folklore lemma about universal hashing which is symmetric to the leftover hash lemma.

Lemma 1

(The injective hash lemma [20]). For any integers a, d, k and l satisfying $a{\le }l$, let Y be any random variable over $\{0, 1\}^{l}$ with ${{\mathbf {H}}_{0}}(Y){\le }a$, and let be a family of $(k{\cdot }2^{-(a+d)})$-almost universal hash functions. Then, we have that

$$\begin{aligned} \Pr _{y{\leftarrow }Y,~h\xleftarrow {\$}\mathcal {H}}[~\exists \tilde{y}\in \mathsf {Supp}(Y):~\tilde{y}\ne {y}~{\wedge }~h(\tilde{y})=h(y) ~]~{\le }~{k}{\cdot }2^{-d}. \end{aligned}$$

Recall that $k=1$ corresponds to the special case that $\mathcal {H}$ is universal.

We also mention the fact that the input and output lengths of a 1-to-1 one-way function $f: \{0, 1\}^{n} \rightarrow \{0, 1\}^{l(n)}$ can be assumed to be linearly related (i.e., $l(n)={O(n)}$). For almost regular one-way functions, we can even assume that they are length-preserving (i.e., $l(n)=n$). We refer to [20] for the proof of Fact 1.

Fact 1

For any $r_1=r_1(n)~\le ~r_2=r_2(n)$ and any efficiently computable $\kappa =\kappa (n)\in {O(n)}$, we have

• 1. Any 1-to-1 (t,$\varepsilon$)-one-way function $f: \{0, 1\}^{n} \rightarrow \{0, 1\}^{l}$ implies a ($t-n^{O(1)}$, $\varepsilon +\mathsf {poly}(n)\cdot {2^{-\kappa }}$)-one-way function $f': \{0, 1\}^{n'\in {\varTheta (n)}} \rightarrow \{0, 1\}^{(n'+\kappa )\in \varTheta (n)}$ which is 1-to-1 except on a $(\mathsf {poly}(n)\cdot {2^{-\kappa }})$-fraction of inputs, i.e.,

  $$\begin{aligned} \Pr _{x\xleftarrow {\$} \{0, 1\}^{n'} }[~\exists {{x'}}\in \{0, 1\}^{n'} :{x'}\ne {x}~\wedge ~f'(x)=f'({x'})~]~\le ~\mathsf {poly}(n)\cdot {2^{-\kappa }} \end{aligned}$$

• 2. Any $(2^{r_1},2^{r_2})$-almost regular (t,$\varepsilon$)-one-way function $f: \{0, 1\}^{n} \rightarrow \{0, 1\}^{l}$ implies a length-preserving ($t-n^{O(1)}$,$\varepsilon +\mathsf {poly}(n)\cdot {2^{-(r_1+\kappa )}}$)-one-way function $\bar{f}: \{0, 1\}^{n'\in {\varTheta (n)}} \rightarrow \{0, 1\}^{n'}$ which is $(2^{\kappa +r_1},2^{\kappa +r_2})$-almost regular except on a $(\mathsf {poly}(n)\cdot {2^{-(r_1+\kappa )}})$-fraction of inputs, i.e.,

  $$\begin{aligned} \Pr _{x\xleftarrow {\$}{ \{0, 1\}^{n'} }}[~2^{\kappa +r_1}~\le ~|\bar{f}^{-1}(\bar{f}(x))|~\le ~{2^{\kappa +r_2}}~]~\ge ~1-\mathsf {poly}(n)\cdot {2^{-(r_1+\kappa )}}. \end{aligned}$$

Therefore, we will assume in the remainder of the paper that the underlying 1-to-1 one-way function has linear output length (i.e., $l(n)=O(n)$) and that the almost-regular and weakly unknown-regular one-way functions are length-preserving (i.e., $l(n)=n$).

3.2 UOWHFs from 1-to-1 OWFs

For a 1-to-1 OWF $f: \{0, 1\}^{n} \rightarrow \{0, 1\}^{l}$, we define a cryptographic game between a challenger $\mathsf{C}$ and an inverter $\mathsf {Inv}$. That is, $\mathsf{C}$ samples a random $y^*\xleftarrow {\$} \{0, 1\}^{l}$ and sends it to $\mathsf {Inv}$, and $\mathsf {Inv}$ wins the game iff he comes up with any $x'$ satisfying $f(x')=y^*$. Note that even unbounded $\mathsf {Inv}$ wins this game with advantage no more than $2^{-(l-n)}$ (which is probability that $y^*\in {f( \{0, 1\}^{n} )}$), and Fact 2 states that the chance to win is even smaller for computationally bounded $\mathsf {Inv}$.

Fact 2

For any 1-to-1 (t,$\varepsilon$)-one-way function $f: \{0, 1\}^{n} \rightarrow \{0, 1\}^{l}$ and any probabilistic algorithm $\mathsf {Inv}$ of running time t, it holds that

$$\begin{aligned} \Pr _{y^{*}\xleftarrow {\$} \{0, 1\}^{l} }[~ f(\mathsf {Inv}(y^{*}))=y^{*} ~]~\le ~2^{-(l-n)}\cdot \varepsilon . \end{aligned}$$

Proof

Remark 1

(on the proof sketch of Theorem 1 ). We use a trick to prove Theorem 1. We show that any $\mathsf{A}$ that $\varepsilon '$-breaks the TCR of the constructed UOWHF implies an $\mathsf {Inv}^{\mathsf{A}}$ (of almost the same efficiency as $\mathsf{A}$) that wins the above game (i.e., inverting f on a random $y^*\in \{0, 1\}^{l}$) with advantage roughly $2^{n-l-s}\cdot \varepsilon '$. This may seem useless since $l-n$ can be $\Omega (n)$ or even $\mathsf {poly}(n)$. However, by Fact 2 this term (i.e., $2^{n-l-s}\cdot \varepsilon '$) is actually upper bounded by $2^{-(l-n)}\cdot \varepsilon$. The conclusion $\varepsilon '{\le }2^s{\varepsilon }$ immediately follows by cancelling the factor $(l-n)$. In other words, the security bound does not depend on the number of bits truncated (i.e., $l-n+s$), but only on shrinkage s, and it is tight due to [5].

Theorem 1

(UOWHFs from 1-to-1 OWFs). Let $f: \{0, 1\}^{n} \rightarrow \{0, 1\}^{l\in {O(n)}}$ be any 1-to-1 (t, $\varepsilon$)-one-way function, let $\mathcal {H}$ be a family of permutations⁶ over $\{0, 1\}^{l}$ as follows:

let be a truncating function, where $s=s(n)$ is efficiently computable. Then, we have that

is a family of ($t-n^{O(1)}$, $2^{s+1}\cdot \varepsilon$)-UOWHFs with key and output length $\varTheta (n)$, and shrinkage s.

Proof

Suppose for contradiction that there exists a $\mathcal {G}_1$-collision finder $\mathsf{A}$ of running time $t'$ that on input (x, h), breaks the target collision resistance with some non-negligible probability $\varepsilon '$, i.e.,

We define algorithm $\mathsf {Inv}^{\mathsf{A}}$ (that inverts f on input $y^*\xleftarrow {\$} \{0, 1\}^{l}$ by invoking $\mathsf{A}$) as in Algorithm 1.

Define event . We argue that $\mathsf {Inv}^{\mathsf{A}}$ inverts f with the following probability (see the rationale below)

where the first inequality is straightforward (note that conditioned on $\mathcal {E}_{\mathsf {neq}}$ the sampling of x and $y^{*}$ are uniform over $\{0, 1\}^{n}$ and $\{0, 1\}^{l} \setminus \{f(x)\}$ respectively), the second inequality follows from Claim 1, namely, conditioned on $\mathcal {E}_{\mathsf {neq}}$ it is equivalent to consider (x, h, v) $\xleftarrow {\$}$ $\{0, 1\}^{n} \times \mathcal {H}\times \mathcal {V}$ and then $y^*:=f(x)-v\cdot {h^{-1}}$, and the third inequality is due to that $\mathsf{A}$ takes only x and h as input (i.e., independent of v). That is, conditioned on that $\mathsf{A}$ produces a valid $x'\ne {x}$ satisfying $h(f(x'))_{[n-s]}=h(f(x))_{[n-s]}$, we have by Claim 1 that string $y^*$ is uniformly distributed over set . Note that the already fixed $f(x')$ is also an element of $\mathcal {Y}^*$ and thus $y^*$ hits $f(x')$ with probability $1/|\mathcal {Y}^*|$=$1/|\mathcal {V}|$. We complete the proof by reaching a contradiction to Fact 2.

Claim 1

(equivalent sampling). Let the values h, v, x, $y^*$ be sampled as in Algorithm 1, and conditioned on event , it is equivalent to sample (x, h, v) $\xleftarrow {\$}$ $\{0, 1\}^{n} \times \mathcal {H}\times \mathcal {V}$ uniformly and independently and then determine $y^*:=f(x)-v\cdot {h^{-1}}$.

Proof of Claim 1. We know that (x, v) is uniformly sampled from $\{0, 1\}^{n} \times \mathcal {V}$ by definition, and thus it suffices to show that “fix any (x, v), and conditioned on $y^*\ne {f(x)}$ (i.e., $Y^*$ is uniform distributed over $\{0, 1\}^{l} \setminus \{f(x)\}$), it holds that h is uniform over $\mathcal {H}$”. This follows from that $v\ne \mathbf {0}$ ($\mathcal {V}$ excludes $\mathbf {0}$ by definition) and hence $h=(f(x)-Y^*)^{-1}\cdot {v}$ is uniform over $\{0, 1\}^{l} \setminus \{\mathbf {0}\}$, namely, $h\xleftarrow {\$}\mathcal {H}$. Finally, for any given (x, h, v), one efficiently determines the value $y^*=f(x)-v\cdot {h^{-1}}$ due to the arithmetics over the finite field.       $\square$

4 UOWHFs from Known Regular OWFs

We proceed to the more general case that f is a known almost-regular function. Recall that by Fact 1 we can assume WLOG that the underlying almost regular one-way function is length-preserving. We first show a construction where the hardness parameter $\varepsilon$ is known, and then remove the dependency on $\varepsilon$.

4.1 Compressing the Output Is Necessary but not Sufficient

We attempt to generalize the Naor-Yung approach for one-way permutations (and 1-to-1 one-way functions) to almost regular one-way functions by compressing (using $\mathsf{trunc}\circ {h}$) the output $Y=f(X)$ into ${{\mathbf {H}}_{\infty }}(Y)-s'$ bits for $s'\in {O(\log \left( {1}/{\varepsilon }\right) )}$. However, this only gives a weak form of guarantee, as stated in Lemma 2 below, that given a random x it is infeasible for efficient algorithms to find any $f(x')\ne {f(x)}$ such that $\mathsf{trunc}({h}(f(x')))=\mathsf{trunc}({h}(f(x)))$. Otherwise said, it does not rule out the possibility that one may easily find $x'\ne {x}$ satisfying $f(x')=f(x)$. Hence, compressing the output is only a useful intermediate step to obtain UOWHFs. Lemma 2 below further generalizes Theorem 1 to known-(almost-)regular functions, whose proof is similar to that of Theorem  ref1-to-1-OWF (see [20]).

Lemma 2

For any constant c, any efficiently computable $r=r(n)$ and $s'=s'(n)$, let $f: \{0, 1\}^{n} \rightarrow \{0, 1\}^{n}$ be any $(2^r,2^r{n^c})$-almost regular (length-preserving) (t, $\varepsilon$)-one-way function, let $\mathcal {H}$ be a family of permutations over $\{0, 1\}^{n}$ as below

let $\mathsf {trunc}: \{0, 1\}^{n} \rightarrow \{0, 1\}^{n-r-c{\cdot }\log {n}-s'}$ be a truncating function. Then, for any $\tilde{\mathsf{A}}$ of running time $t-n^{O(1)}$ (for some universal constant O(1)) we have that

4.2 Known (Almost-)Regular OWFs with Known Hardness

We first give an optimal construction assuming that the inversion probability upper bound $\varepsilon$ is known. Note that in addition to hashing the output f(x) (as we did in Lemma 2), we also hash the input x to ensure that no distinct $x'$ collides with x with respect to the resulting function.

Theorem 2

(UOWHFs from known-almost-regular $\varepsilon$-hard OWFs).  Let $f: \{0, 1\}^{n} \rightarrow \{0, 1\}^{n}$ be any $(2^r,2^r{n^c})$-almost regular (length-preserving) (t,$\varepsilon$)-one-way function as assumed in Lemma 2. Let shrinkage $s=s(n)$ be any efficiently computable function, and let $\mathcal {H}$ and $\mathsf{trunc}$ be as defined in Lemma 2 with $s'=(s+\log (1/\varepsilon )-c\log {n})/2$, and let $\mathcal {H}_1=\{h_1: \{0, 1\}^{n} \rightarrow \{0, 1\}^{r+c\log {n}+s'-s} \}$ be a family of universal hash functions. Then, we have that

where , is a ($t-n^{O(1)}$, $O(\sqrt{2^s\cdot {n^c}\cdot \varepsilon })$)-universal one-way hash function family with key and output length $\varTheta (n)$.

Proof

Define shorthands and . For any $\mathcal {G}_2$-collision finder $\mathsf{A}$, we have

where the first inequality refers to that any collision on $g\in \mathcal {G}_2$ (for $x'\ne {x}$) must satisfy either $\mathcal {E}_1$ or $\mathcal {E}_2$ and the second inequality follows by a union bound. We already know by Lemma 2 that the second term is bounded by $n^c{\cdot }2^{s'+1}\varepsilon$, and it thus remains to show that the first term is bounded by $2^{-(s'-s)}$. Conditioned on any $y=f(X)$ random variable X is a flat distribution on a set of size at most $2^r{\cdot }n^c$, so we apply Lemma 1 (setting $a=r+c\cdot {\log }n$, $d{\ge }s'-s$ and $k=1$) to get

which completes the proof.

4.3 An Alternative Approach to Sect. 4.2

A neater (and perhaps more intuitive) approach is to construct an almost 1-to-1 one-way function $f'$ (with input and output lengths $\varTheta (n)$) based on f (stated as Theorem 3) and then plug $f'$ into Theorem 1 (using $f'$ in place of f)⁷. This statement is interesting in its own right as it implies that almost 1-to-1 one-way functions and known-(almost-)regular one-way functions (with known hardness) are equivalent. Taking a closer look at Theorem 3 we find that this almost 1-to-1 $f'$ is also present (as an intermediate function) in construction $\mathcal {G}_2$ of Theorem 2 (except with slightly different length parameters). Lemmas 3 and 4 state the almost injectiveness and one-way-ness of $f'$ respectively, for which we determine a judicious value for d (assuming knowledge about $\varepsilon$) in Theorem 3 to achieve injectiveness and one-way-ness simultaneously.

Theorem 3

(almost 1-to-1 OWF from almost-regular $\varepsilon$ -hard OWF). Let $f: \{0, 1\}^{n} \rightarrow \{0, 1\}^{n}$ be any $(2^r,2^r{n^c})$-almost regular (length-preserving) (t,$\varepsilon$)-one-way function as assumed in Lemma 2. For efficiently computable $d=d(n)\in \mathbb {N}$, define

$$\begin{aligned} f': \{0, 1\}^{n} \times \mathcal {H}_1\rightarrow \{0, 1\}^{n} \times \{0, 1\}^{r+c\cdot {\log {n}}+d} \times \mathcal {H}_1 \end{aligned}$$

where $\mathcal {H}_1$ is a family of universal hash functions from n bits to $r+c{\cdot }{\log {n}}+d$ bits. Then, for $d=\frac{\log (1/\varepsilon )-c\cdot \log {n}-3}{3}$ we have that $f'$ is 2$\root 3 \of {\varepsilon \cdot {n^c}}$-almost 1-to-1 and ($t-O(n)$, 2$\root 3 \of {\varepsilon \cdot {n^c}}$)-one-way with input and output lengths $\varTheta (n)$.

Proof

The almost 1-to-1-ness and one-way-ness of $f'$ follow from Lemmas 3 and 4 respectively by setting parameter $d=\frac{\log (1/\varepsilon )-c\cdot \log {n}-3}{3}$.

Lemma 3

( $f'$ is almost 1-to-1 [20]). $f'$ defined in Therorem 3 is $2^{-d}$-almost 1-to-1.

Lemma 4

( $f'$ is one-way [20]). $f'$ defined in Therorem 3 is a ($t-O(n)$, $\sqrt{2^{d+3}\cdot {n^c}\cdot \varepsilon }$)-one-way function.

4.4 UOWHFs from any Known (Almost-)Regular OWFs

Removing the dependency on $\varepsilon$. Unfortunately, Theorem 2 doesn’t immediately apply to an arbitrary regular function as in general we assume no knowledge about $\varepsilon$ (other than that $\varepsilon$ is negligible). To see the difficulty, check the proof of Theorem 2 where the security of the resulting UOWHF is bounded by the sum of two terms, i.e., $2^{-(s'-s)} ~+~n^c{\cdot }2^{s'+1}\cdot \varepsilon$. Without knowing $\varepsilon$, one may end up setting some super-polynomial $2^{s'}$ (to make the first term negligible) which kills the second term $n^c{\cdot }2^{s'+1}\cdot \varepsilon$. Same problems arise in similar situations (e.g., construction of PRGs from regular OWFs [22]). A remedy for this is parallel repetition: run $q\in \omega (1)$ copies of f on $\mathbf {x}=(x_1,\ldots ,x_q)$, apply hash-then-truncate (setting $s'=2\log {n}$) to every copy $f(x_i)$, which shrinks the entropies by $2q\log {n}$ bits and yields a bound $O(\varepsilon {\cdot }n^{c+2})$. Next, apply a single hashing to $\mathbf {x}$ that expands $q{\cdot }\log {n}$ bits (to yield another negligible term $n^{-q}$). This gives a family of UOWHFs with shrinkage $2q\log {n}-q\log {n}=q\log {n}$, and key and output length $O(q\cdot {n})$ for any (efficiently computable) $q\in \omega (1)$. The proof is similar in spirit to that of Theorem 2 (see [20]).

Definition 8

(parallel repetition). For any function $g:\mathcal {X}\rightarrow \mathcal {Y}$, we define its q-fold parallel repetition $g^q:\mathcal {X}^q\rightarrow \mathcal {Y}^q$ as

$$\begin{aligned} g^q(x_1,...,x_q) = (~g(x_1)~,...,~g(x_q)~). \end{aligned}$$

For simplicity, we use shorthand and thus $g^q(\mathbf {x}){=}g^q(x_1,\ldots ,x_q)$.

Theorem 4

(UOWHFs from any known almost-regular OWFs). Let $f: \{0, 1\}^{n} \rightarrow \{0, 1\}^{n}$ be any $(2^r,2^r{n^c})$-almost regular (length-preserving) (t,$\varepsilon$)-one-way function as assumed in Lemma 2. Then, for any efficiently computable $q=q(n)=\omega (1)$, let $\mathcal {H}$ and $\mathsf{trunc}$ be as defined in Lemma 2 with $s'=2\log {n}$, and let $\mathcal {H}_1=\{h_1: \{0, 1\}^{q{\cdot }n} \rightarrow \{0, 1\}^{q(r+(c+1)\log {n})} \}$ be a family of universal hash functions, we have that

where , is a ($t-n^{O(1)}$,${n^{-q}}+2q{\cdot }n^{c+2}\cdot \varepsilon$)-universal one-way hash function family with key and output length $O(q\cdot {n})$, and shrinkage $q{\cdot }\log {n}$.

5 Going Beyond Almost-Regular OWFs

Although (almost) optimal, our foregoing constructions need at least almost-regularity, i.e., the one-way function f satisfies $\alpha \le |f^{-1}(f(x))|\le \alpha \cdot \beta$ for all (or at least an overwhelming portion of) x, where $\alpha$ is efficiently computable and $\beta =\mathsf {poly}(n)$ (or at most $\beta =O(\log \left( {1}/{\varepsilon }\right) )$ for an ($\varepsilon ^{-1}$,$\varepsilon$)-hard f). Complementary to our work, Ames et al. [1] gave an elegant construction from unknown-(almost-)regular one-way functions, namely, without knowledge about $\alpha$, for which they pay a cost of much increased number of one-way function calls (i.e., $O(n/{\log }n)$) and key length $O(n\log {n})$. In this section, we further weaken the assumption so that f can have an arbitrary structure (i.e., $\beta$ is not bounded) as long as the fraction of x’s with (nearly) maximal number of siblings is noticeable.

5.1 A More General Class of OWFs

The following class of one-way functions was introduced in [21] as a relaxation to unknown-(almost-)regular one-way functions.

Definition 9

(weakly unknown-regular OWFs [21]). Let $f: \{0, 1\}^{n} \rightarrow \{0, 1\}^{l(n)}$ be a one-way function, and for every $n\in \mathbb {N}$, divide domain $\{0, 1\}^{n}$ into sets $\mathcal {X}_1,\ldots ,\mathcal {X}_n$ (i.e., $\mathcal {X}_1\cup \ldots \cup \mathcal {X}_n= \{0, 1\}^{n}$) such that , and define $\max =\max (n)$ to be the maximal subscript of the non-empty sets, i.e., $|\mathcal {X}_{\max }|>0$ and $|\mathcal {X}_{\max +1}\cup \ldots \cup \mathcal {X}_{n}|=0$. We say that f is weakly unknown-regular if there exists a constant c such that for all sufficiently large n:

$$\begin{aligned} \Pr [U_n\in \mathcal {X}_{\max }]\ge {n^{-c}}. \end{aligned}$$

(1)

Note that $\max (\cdot )$ can be arbitrary (not necessarily efficient) functions and thus unknown-regular one-way functions fall into a special case⁸ for $c=0$.

5.2 UOWHFs from Beyond Almost-Regular OWFs

We state below the main results of this section, namely, the fourth construction which is based on weakly unknown-regular one-way functions (see Definition 9).

Theorem 5

Assume that f is a weakly unknown-regular one-way function on an $n^{-c}$-fraction of domain for constant c. Then, there exists an explicit construction of UOWHF family with output length $\varTheta (n)$, key length $O(n\cdot {\log }n)$ by making $n^{2c+1}\cdot \omega (1)$ black-box calls to f.

The main idea is to transform any weakly unknown-regular one-way function f into a family of functions $\mathcal {F}=\{f_u:u\in \{0, 1\}^{O(n\log {n})} \}$ such that ${\mathcal {F}}$ is almost regular and that it preserves the one-way-ness of f. $\mathcal {F}$ is constructed based on (the derandomized version of) the randomized iterate with a succinct description u. Finally, we sample a random $f_u\xleftarrow {\$}\mathcal {F}$ and plug it into the construction by Ames et al. to get the UOWHFs as desired. We refer to [20] for more details about the explicit construction.

Definition 10

(the randomized iterate [7, 10]). Let $n\in \mathbb {N}$, function $f: \{0, 1\}^{n} \rightarrow \{0, 1\}^{n}$, and let $\mathcal {H}$ be a family of pairwise-independent length-preserving hash functions over $\{0, 1\}^{n}$. For $k\in \mathbb {N}$, $x_1\in \{0, 1\}^{n}$ and vector $\mathbf {h}^{k}$ = $(h_1,\ldots ,h_{k})\in \mathcal {H}^{k}$, recursively define the $i^{th}$ randomized iterate by:

$$\begin{aligned} y_i=f(x_i), ~x_{i+1}= h_{i}(y_i). \end{aligned}$$

We denote the $i^{th}$ iterate by function $f^i$, i.e., $y_i~=~f^i(x_1,\mathbf {h}^{k})$, where $\mathbf {h}^{k}$ is possibly redundant as for $i\le {k+1}$ $y_i$ only depends on $\mathbf {h}^{i-1}$.

The randomized version refers to the case where $x_1\xleftarrow {\$} \{0, 1\}^{n}$ and $\mathbf {h}^{k}\xleftarrow {\$}\mathcal {H}^{k}$.

The derandomized version refers to that $x_1\xleftarrow {\$} \{0, 1\}^{n}$, $u\xleftarrow {\$} \{0, 1\}^{q\in {O}(n{\cdot }{\log }n)}$, $\mathbf {h}^{k}:=BSG(u)$, where $BSG: \{0, 1\}^{q} \rightarrow \{0, 1\}^{k\cdot {\log |\mathcal {H}|}}$ is a bounded-space generator that $2^{-2n}$-fools every $(2n+1,k,\log |\mathcal {H}|)$-LBP (layered branching program), and $\log |\mathcal {H}|$ is the description length of $\mathcal {H}$ (e.g., 2n bits for concreteness).

Remark 2

(on what is proven in [21]). The authors of [21] introduced weakly unknown-regular one-way functions from which they constructed a pseudorandom generator with seed length $O(n\cdot \log {n})$ based on the randomized iterate. They showed that “every $k=n^{2c}\cdot {\log {n}}\cdot \omega (1)$ iterations are hard-to-invert”, i.e., for any j it is hard to predict $x_j$ given $y_{j+k}=f^{j+k}(x_1,BSG(u))$ and u. A PRG thus follows by outputting $\log {n}$ hardcore bits for every k iterations. In this paper, we first adapt their findings to show that $f_u(\cdot )=f^k(\cdot ,BSG(u))$ constitutes a family of one-way functions, i.e., given $y_k=f_u(x_1)$ and u it is infeasible to find any $x_1'$ such that $y_k=f^k(x_1',BSG(u))$. This is stated as Lemma 6. However, it is still insufficient to construct UOWHFs with the one-way-ness of $f_u$. We further show in Lemma 7 that a random $f_u\xleftarrow {\$}\mathcal {F}$ is almost regular (in a slightly weaker sense than Definition 6 but already suffices for our needs).

Following [21], we define the following event and recall some inequalities.

Definition 11

For any $n,j{\le }k\in \mathbb {N}$, define events

where , and $(X_1,U_q)$ are uniform over $\{0, 1\}^{n} \times \{0, 1\}^{q}$. Note that by definition $\mathcal {Y}_{\max }=f(\mathcal {X}_{\max })$ (see Definition 9) and thus $\Pr [f(U_n)\in \mathcal {Y}_{\max }]\ge {n^{-c}}$.

Lemma 5

(Some inequalities from [20])

$$\begin{aligned} \mathsf {CP}(~Y'_{k}~|~U_q)~\le ~k{\cdot }2^{{\max }-n+1}+2^{-2n}, \end{aligned}$$

(2)

$$\begin{aligned} \Pr [\mathcal {E}'_{1} \vee \mathcal {E}'_{2} \vee \ldots \vee \mathcal {E}'_{k}]~\ge ~1-2^{-k/n^{2c}}-2^{-2n}~, \end{aligned}$$

(3)

where .

Lemma 6

( $\mathcal {F}$ is one-way [20]). Assume that f is a $(t,\varepsilon )$-OWF that is weakly unknown-regular on an $n^{-c}$ fraction of domain, define a family of functions

$$\begin{aligned} \mathcal {F}\mathop {=}\limits ^{{{\tiny {def}}}}\{~f_{u}: \{0, 1\}^{n} \rightarrow \{0, 1\}^{n} ,f_{u}(x){=}f^k(x,BSG(u)),u\in \{0, 1\}^{O(n{\cdot }\log {n})} ~\} \end{aligned}$$

(4)

where $\mathcal {H}$,$f^k$ and $BSG: \{0, 1\}^{q{\in }O(n\cdot {\log {n}})}$ $\rightarrow$ $\{0, 1\}^{k\cdot {\log |\mathcal {H}|}}$ are as defined in Definition 10. Then, for any $\mathsf{A}$ of running time $t-n^{O(1)}$ it holds that

(5)

Lemma 7

( $\mathcal {F}$ is almost-regular). Let $\mathcal {F}=\{f_u\}$ be as defined in Lemma 6. Then, for any $a\ge {0}$ it holds that

(6)

where $u\in \{0, 1\}^{q{\in }O(n\cdot {\log {n}})}$ and $f_{u}(x){=}f^k(x,BSG(u))$.

Proof

We define and , where $X_1$ is uniform over $\{0, 1\}^{n}$. The left-hand of (6) is lower bounded by $1-\Pr [\mathcal {S}_{low}]-\Pr [\mathcal {S}_{up}]$ and thus it suffices to upper bound both $\Pr [\mathcal {S}_{low}]$ and $\Pr [\mathcal {S}_{up}]$. We have

where the first inequality is trivial, the second is by the union bound and (3), and the third is due to that for every $j\in [k]$ with shorthand it holds that

where the first inequality is due to Fact 3 (setting $f_1$=$f_{u,j}$, $f_2=f{\circ }h_{k-1}{\circ }\ldots {\circ }{f}\circ {h_j}$ and thus $\bar{f}=f_u$), the second follows from the fact that there are $|\mathcal {Y}_{\max }|$ possible values for $f_{u,j}(x)\in \mathcal {Y}_{\max }$ and every $f_{u,j}(x)$ has less than $2^{\max -a-1}$ preimages (by definition of $\mathcal {S}_{low}$), and the third is due to $|\mathcal {Y}_{\max }|{\le }2^{n+1-\max }$. Next we proceed to bounding the second term, i.e., $\Pr [\mathcal {S}_{up}]~\le ~k{\cdot }2^{-a+1}$.

where the first inequality is by (2), and the second is due to that for any (y, u) satisfying $|f_u^{-1}(y)|>2^{\max +a+1}$ and it holds that

$$\begin{aligned} \Pr [~f_u(X_1)=y~|~U_q=u]~=~\Pr [~X_1~{\in }~f_u^{-1}(y)~]~>2^{-n}{\cdot }2^{{\max }+a+1}=2^{{\max }+a-n+1}. \end{aligned}$$

It follows that $\Pr [\mathcal {S}_{up}]\le (k{\cdot }2^{{\max }-n+1}+2^{-2n})/2^{{\max }+a-n+1}{\le }k{\cdot }2^{-a+1}$ and hence completes the proof.

Fact 3

Let $f_1:\mathcal {X}\rightarrow \mathcal {Y}$ and $f_2:\mathcal {Y}\rightarrow \mathcal {Z}$ be any functions, and let . Then for any $t\in \mathbb {N}^+$ it holds that

$$\begin{aligned} \{x:0<|\bar{f}^{-1}(\bar{f}(x))|<t\} ~\subseteq ~\{x:0<|f_1^{-1}(f_1(x))|<t\}. \end{aligned}$$

Proof

Any x satisfying $0<|\bar{f}^{-1}(\bar{f}(x))|<t$ implies $0<|f_1^{-1}(f_1(x))|<t$.

Given that $\mathcal {F}$ is a family of unknown-(almost-)regular one-way functions with description length $O(n\cdot \log {n})$, we just plug a random $f_u\in \mathcal {F}$ into the Ames et al.’s construction [1] to yield a family of UOWHFs with output length $\varTheta (n)$ and key length $O(n\cdot \log {n})$. We refer to a more complete version of this work [20], where we put together all the necessary technical details.