Cryptography Reference
In-Depth Information
applying
f
to
U
n
will yield a great loss in “entropy” that cannot be compensated by
using the foregoing
m
ethods. For example, if
f
(
x
,
y
)
def
=
f
(
x
)0
|
y
|
for
|
x
|=|
y
|
then
2
−
|
α
|
2
for some
Pr
's. In this case, achieving uniform distribution from
f
(
U
n
) requires shrinking it to length approximately
n
[
f
(
U
n
)
=
α
]
≥
α
2. In general, we cannot com-
pensate for these lost bits (using the foregoing methods), because
f
may not have a
hard-core with such a huge range (i.e., a hard-core
g
satisfying
/
|
>
|
α
|
2
|
g
(
α
)
). Hence,
in this case, a new idea is needed and indeed is presented next.
The idea is that in case
f
maps different pre-images into the same image
y
,we
can augment
y
by the index of the pre-image in the set
f
−
1
(
y
),
without damaging
the hardness-to-invert of f
. Namely, we define
F
(
x
)
def
=
f
(
x
)
·
idx
f
(
x
), where idx
f
(
x
)
x
:
f
(
x
)
denotes the index (say by lexicographic order) of
x
in the set
.We
claim that inverting
F
is not substantially easier than inverting
f
. This claim can be
proved by a reducibility argument. Given an algorithm for inverting
F
, we can invert
f
as follows. On input
y
(supposedly in the range of
f
(
U
n
)), we first select
m
uniformly
in
{
1
,...,
n
}
, next select
i
uniformly in
{
1
,...,
2
m
{
=
f
(
x
)
}
}
, and finally try to invert
F
on (
y
,
i
).
When analyzing this algorithm, consider the case
i
=
log
2
|
f
−
1
(
y
)
|
.
The suggested function
F does preserve the hardness-to-invert of f
. The problem is
that
F does not preserve the easy-to-compute property of f
. In particular, for general
f
, it is not clear how to compute idx
f
(
x
); the best we can say is that this task can be
performed in exponential time (and polynomial
space
). Again, hashing functions come
to the rescue. Suppose, for example, that
f
is 2
m
-to-1 on strings of length
n
. Then we can
let idx
f
(
x
)
=
(
H
n
,
H
n
(
x
)), obtaining “probabilistic indexing” of the set of pre-images.
We stress that applying this idea requires having a good estimate for the size of the set of
pre-images (of a given image). That is, given
x
, it should be easy to compute
|
f
−
1
(
f
(
x
))
|
.
A simple case where such an estimate is handy is the case of regular functions.
Definition 3.5.7 (Regular Functions):
A function f
:
{
0
,
1
}
∗
→{
0
,
1
}
∗
is called
regular
if there exists an integer function m
:
N→N
such that for all sufficiently
long x
∈{
0
,
1
}
∗
, it holds that
2
m
(
|
x
|
)
|{
y
:
f
(
x
)
=
f
(
y
)
∧|
x
|=|
y
|}| =
For simplicity, the reader can further assume that there exists an algorithm that on input
n
computes
m
(
n
) in poly(
n
) time. As we shall see at the end of this subsection, one can
do without this assumption. For the sake of simplicity (of notation), we assume in the
sequel that if
f
(
x
)
=
f
(
y
), then
|
x
|=|
y
|
.
Construction 3.5.8:
Let f
:
{
0
,
1
}
∗
→{
0
,
1
}
∗
be a regular function, with m
(
|
x
|
)
=
log
2
|
f
−
1
(
f
(
x
))
|
for some integer function m
(
·
)
. Let l
:
N→N
be an integer func-
tion, and S
m
(
n
)
−
l
(
n
)
n
a hashing family. For every x
∈{
0
,
1
}
n
and h
∈
S
m
(
n
)
−
l
(
n
)
n
,
define
h
)
def
F
(
x
,
=
(
f
(
x
)
,
h
(
x
)
,
h
)
If
f
can be computed in polynomial time and
m
(
n
) can be computed from
n
in poly(
n
)
time, then
F
can be computed in polynomial time. We now show that if
f
is a regular
142
