Cryptography Reference
In-Depth Information
looking” function
f
s
(determining 2
n
-many values), merely need to gen-
erate and share among themselves the
n
-bit seed
s
.(Forexample,one
party may randomly select the seed
s
, and communicate it, via a secure
channel, to all other parties.) Sharing a pseudorandom function allows
parties to determine (by themselves and without any further commu-
nication) random-looking values depending on their current views of
the environment (which need not be known a priori). To appreciate the
potential of this tool, one should realize that sharing a pseudorandom
function is essentially as good as being able to agree, on the fly, on the
association of random values to (on-line) given values, where the latter
are taken from a huge set of possible values. We stress that this agree-
ment is achieved without communication and synchronization: When-
ever some party needs to associate a random value to a given value,
v
n
(by setting
r
v
=
f
s
(
v
), where
f
s
is a pseudorandom function agreed
upon beforehand).
n
, it will associate to
v
the (same) random value
r
v
∈{
∈{
0
,
1
}
0
,
1
}
Theorem 3.5.
((68), see (65, Sec. 3.6.2)):
Pseudorandom functions
can be constructed using any pseudorandom generator.
Proof sketch:
Let
G
be a pseudorandom generator that stretches its
seed by a factor of two (i.e.,
(
n
)=2
n
), and let
G
0
(
s
)(resp.,
G
1
(
s
))
denote the first (resp., last)
bits in
G
(
s
). Define
G
σ
|s|
···σ
2
σ
1
(
s
)
de
=
G
σ
|s|
(
|
s
|
···
G
σ
2
(
G
σ
1
(
s
))
···
)
.
}
|s|
}
s∈{
0
,
1
}
∗
,
where
f
s
(
x
)
de
=
G
x
(
s
). Pictorially, the function
f
s
is defined by
n
-step
walks down a full binary tree of depth
n
having labels at the vertices.
The root of the tree, hereafter referred to as the level 0 vertex of the
tree, is labeled by the string
s
. If an internal vertex is labeled
r
then
its left child is labeled
G
0
(
r
) whereas its right child is labeled
G
1
(
r
).
The value of
f
s
(
x
) is the string residing in the leaf reachable from the
root by a path corresponding to the string
x
.
We claim that the function ensemble
}
|s|
→{
We consider the function ensemble
{
f
s
:
{
0
,
1
0
,
1
f
s
}
s∈{
0
,
1
}
∗
, defined above, is
pseudorandom. The proof uses the hybrid technique: The
i
th
{
hybrid,
