Cryptography Reference
In-Depth Information
}
∗
,it
N → N
and a polynomial q
(
·
)
such that for all sufficiently long x
∈{
0
,
1
holds that
2
m
(
|
x
|
)
2
m
(
|
x
|
)
≤|{
y
:
f
(
x
)
=
f
(
y
)
}| ≤
q
(
|
x
|
)
·
When using these (relaxed) regular functions in Construction 3.5.8, set
m
(
n
)
def
m
(
n
).
The resulting function
F
will have a slightly weaker “almost” 1-1 property. Namely,
=
F
−
1
F
U
n
,
H
m
(
n
)
−
l
(
n
)
>
q
(
n
)
2
l
(
n
)
+
1
<
2
−
(
l
(
n
))
Pr
·
n
The application of Construction 3.5.2 will be modified accordingly. We get the
following:
Theorem 3.5.11:
If there exist regular one-way functions, then pseudorandom
generators exist as well.
3.5.3. Going Beyond Regular One-Way Functions
The proof of Proposition 3.5.9 relies heavily on the fact that the one-way function
f
is regular (at least in the weak sense). Alternatively, Construction 3.5.8 needs to be
modified so that different hashing families are associated with different
x
∈{
0
,
1
}
n
.
Furthermore, the argument leading to Theorem 3.5.6 cannot be repeated unless it is
easy to compute the cardinality of set
f
−
1
(
f
(
x
)) given
x
. Note that this time we cannot
construct functions
F
m
for every possible value of
log
2
|
f
−
1
(
y
)
|
, because none of the
functions may satisfy the statement of Proposition 3.5.9. Again, a new idea is needed.
A key observation is that although the value of log
2
|
f
−
1
(
f
(
x
))
|
may vary for dif-
n
, the value
m
(
n
)
def
=
E
(log
2
|
f
−
1
(
f
(
U
n
))
|
) is unique. Furthermore, the
ferent
x
∈{
0
,
1
}
function
f
defined by
f
(
x
1
,...,
x
n
2
)
def
=
f
(
x
1
)
,...,
f
(
x
n
2
)
where
n
, has the property that all but a negligible fraction of the
domain resides in pre-image sets, with the logarithm
of
their cardinalit
y
not
d
eviating
too muc
h
from the expected value. Specifically, let
m
(
n
3
)
def
|
x
1
|=···=|
x
n
2
|=
f
−
1
(
f
(
U
n
3
))
=
E
(log
2
|
|
).
Clearly,
m
(
n
3
)
n
2
=
·
m
(
n
). Using the Chernoff bound, we get
[
|
m
(
n
3
)
−
log
2
|
f
−
1
(
f
(
U
n
3
))
||
>
n
2
]
<
2
−
n
Suppose w
e a
pply Construction 3.5.8 to
f
, setting
l
(
n
3
)
def
Pr
=
n
2
. D
enote the resulting
function
by
F
.
Suppose
we
apply
Construction
3.5.2
to
F
,
this
time
setting
l
(
n
3
)
def
1. Using the ideas presented in the proofs of Propositions 3.5.3 and 3.5.9,
we can show that if the fu
nc
tion mapping
n
3
=
2
n
2
−
1 bits used in Construc-
tion 3.5.2 is a hard-core of
F
, then the resulting algorithm constitutes a pseudorandom
ge
nerator. Yet, we
ar
e left with the
pro
blem of constructing a huge hard-core function
G
for the f
unc
tion
F
. Specifically,
bits to
l
(
n
3
)
+
2
3
for all
x
's. A natural idea
is to define
G
analogously to the way
g
is defined in Construction 3.5.4. Unfort
un
ately,
we do not know how to prove the validity of this construction (when applied to
F
), and
a much more complicated construction is required. This construction does use all the
147
|
G
(
x
)
|
has to equal 2
|
x
|
