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,   Search WWH ::

Custom Search