Cryptography Reference
In-Depth Information
Construction 3.6.5:
Let G be a deterministic algorithm that expands inputs of
length n into strings of length
2
n. We denote by G
0
(
s
)
the
|
s
|
-bit-long prefix of
G
(
s
)
, and by G
1
(
s
)
the
|
s
|
-bit-long suffix of G
(
s
)(
i.e., G
(
s
)
=
G
0
(
s
)
G
1
(
s
))
.For
n
, we define a function f
s
:
{
0
,
1
}
n
n
every s
∈{
0
,
1
}
→{
0
,
1
}
such that for every
σ
1
,...,σ
n
∈{
0
,
1
}
,
G
σ
n
···
G
σ
2
G
σ
1
(
s
)
···
That is, on input s and x
=
σ
1
σ
2
···
σ
n
, the value f
s
(
x
)
is computed as follows:
σ
1
σ
2
···
σ
n
)
def
f
s
(
=
Let y
=
s
.
Fo r i
=
1
to n
,
do
y
←
G
σ
i
(
y
)
.
Output y
.
Let F
n
be a random variable defined by uniformly selecting s
∈{
0
,
1
}
n
and setting
F
n
=
f
s
. Finally, let F
={
F
n
}
n
∈N
be our function ensemble.
Pictorially (see Figure 3.5), 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
We let
s
λ
=
s
and
s
ασ
=
G
σ
(
s
α
). The value of
=
s
σ
1
σ
2
···
σ
n
is
obtained at the leaf reachable from the root (labeled
s
) by following the path
σ
1
σ
2
···
σ
n
.
σ
1
σ
2
···
σ
n
)
f
s
(
s
0
1
s
1
s
0
1
1
0
0
s
00
s
01
s
1
s
1
0
1
0
0
1
1
0
1
0
1
s
s
s
s
s
100
s
101
s
s
111
000
001
010
011
110
=
s
001
=
G
1
(
s
00
)
=
G
1
(
G
0
(
s
0
))
=
G
1
(
G
0
(
G
0
(
s
))).
For example,
f
s
(001)
Figure 3.5:
Construction 3.6.5, for n
=
3
