![](https://csdnimg.cn/release/download_crawler_static/16066846/bg5.jpg)
(Almost) Optimal Constructions of UOWHFs from 1-to-1 213
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 num-
ber 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 ·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 respec-
tive one-way function f : {0, 1}
n
→{0, 1}
l
introduced above. We note that the
following assumptions (about output length) can be made without loss of gen-
erality: l ∈ 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
→{0, 1}
l
implies a one-way function f
: {0, 1}
n
∈Θ(n)
→
{0, 1}
l
∈Θ(n)
that is 1-to-1 except for a negligible fraction. Any one-way function
f with α ≤|f
−1
(y)|≤α·β implies another length-preserving one-way function
f
: {0, 1}
n
∈Θ(n)
→{0, 1}
n
with α
≤|f
−1
(y)|≤α
·β except for a negligible
fraction, where the size of range β is preserved, and α
is efficiently computable
if α is. We refer to [20]forafullproof.
Based o n 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:
G
1
def
= { (trunc ◦ h ◦ f):{0, 1}
n
→{0, 1}
n−s
,h∈H},
where H is a family of universal hash permutations on l bits, and trunc : {0, 1}
l
→
{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,ε)- 1-to-1 OWF then the resulting G
1
is a (t − n
O(1)
,
2
s+1
· ε)-UOWHF family with key and output length Θ(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 ε-hard OWFs. Given an almost-
regular f (see Definition 6)whichisknowntobe(t,ε)-one-way for some efficiently
computable ε, we define the following function family
G
2
def
= { g : {0, 1}
n
→{0, 1}
n−s
,g(x)=(trunc(h(f (x))),h
1
(x)),h ∈H,h
1
∈H
1
}
where H is a family of universal hash permutations, and let H
1
and trunc be
a family of universal hash functions and the truncating function (both with