Cryptography Reference
In-Depth Information
the shrunk result will induce a uniform distribution. The question is how to
efficiently
carry out this shrinking process.
Suppose that there exists an efficiently computable function
h
such that
f
h
(
x
)
def
=
h
(
f
(
x
)) is length-preserving and 1-1. In such a case we can let
G
(
s
)
def
b
(
s
),
where
b
is a hard-core predicate for
f
, and get a pseudorandom generator. The pseu-
dorandomness of
G
follows from the observation that if
b
is a hard-core for
f
,itis
also a hard-core for
f
h
(since an algorithm guessing
b
(
x
) from
h
(
f
(
x
)) can be easily
modified so that it guesses
b
(
x
) from
f
(
x
), by applying
h
first). The problem is that
we “know nothing about the structure” of
f
and hence are not guaranteed that such an
h
exists. An important observation is that a uniformly selected “hashing” function will
have approximately the desired properties. Hence, hashing functions play a central role
in the construction, and consequently we need to discuss these functions first.
=
h
(
f
(
s
))
·
3.5.1.1. Hashing Functions
Let
S
n
be a set of strings representing functions mapping
n
-bit strings to
m
-bit strings.
For simplicity we assume that
S
n
={
l
(
n
,
m
)
for some function
l
. In the sequel, we
freely associate the strings in
S
n
with the functions that they represent. Let
H
n
be a
random variable uniformly distributed over the set
S
n
. We call
S
n
a
hashing family
(or
a
family of hashing functions
) if it satisfies the following three conditions:
0
,
1
}
1.
S
n
is a pairwise-independent family of mappings
: For every
x
=
y
∈{
0
,
1
}
n
, the random
variables
H
n
(
x
) and
H
n
(
y
) are independent and uniformly distributed in
m
.
{
0
,
1
}
2.
S
n
m
)
.
3.
S
n
can be efficiently evaluated
: There exists a polynomial-time algorithm that on input
a representation of a function
h
(in
S
n
has succinct representation
:
S
n
={
poly(
n
,
0
,
1
}
n
) and a string
x
∈{
0
,
1
}
returns
h
(
x
).
We stress that hashing families as defined here carry no hardness requirement and exist
independently of any intractability assumption.
3
One widely used hashing family is the
set of affine transformations mapping
n
-dimensional binary vectors to
m
-dimensional
ones (i.e., transformations effected by multiplying the
n
-dimensional vector by an
n
-by-
m
binary matrix and adding an
m
-dimensional vector to the result). A hashing family
with more succinct representation is obtained by considering only the transformations
effected by Toeplitz matrices (i.e., matrices that are invariant along the diagonals). For
further details, see Exercise 22.
The following lemma concerning hashing functions is central to our analysis (as
well as to many applications of hashing functions in complexity theory). Loosely
speaking, the lemma asserts that if a random variable
X
n
does not assign too much
probability mass to any single string, then most
h
's in a hashing family will have
h
(
X
n
)
distributed almost uniformly. Specifically, when using a hashing family
S
n
, as earlier,
we shall consider only random variables
X
n
satisfying
Pr
2
−
m
, for every
[
X
n
=
x
]
n
.
x
∈{
0
,
1
}
3
In contrast, notions such as collision-free hashing and universal one-way hashing have a hardness requirement
and exist only if one-way functions exist. (Collision-free hashing and universal one-way hashing will be defined
and discussed in Chapter 6, which will appear in Volume 2.)
