Cryptography Reference
In-Depth Information
f
k
(3)
...
If we take these values as the output values of a PRBG (seeded with
k
), then
the resulting PRF-based PRBG can be specified as follows:
G
(
k
)=
f
k
(0)
,f
k
(1)
,f
k
(2)
,f
k
(3)
,...
=(
f
k
(
i
))
i≥
0
If we assume the PRF family
F
to be secure (in the sense mentioned earlier),
then the corresponding PRF-based PRBG
G
(
k
) can also be shown to be crypto-
graphically secure. The efficiency of this PRBG mainly depends on the efficiency of
the underlying PRF family (i.e., the PRF-based PRBG is efficient if the instances of
the underlying PRF family can be implemented efficiently).
13.2.2
PRBG-Based PRF
More suprisingly, if we ask whether it is possible to construct a PRF family using
a PRBG, then we can also answer in the affirmative. The first construction was
proposed by Oded Goldreich, Shafi Goldwasser, and Silvio Micali in the 1980s [1].
Let
G
(
s
) be a PRBG with stretching function
l
(
n
)=2
n
,
G
0
(
s
)(
G
1
(
s
)) be the
first (last)
n
bits of
G
(
s
) for
s
n
,
X
=
Y
=
n
,and
x
=
σ
n
···
∈{
0
,
1
}
{
0
,
1
}
σ
2
σ
1
the bitwise representation of
x
. A simple PRBG-based PRF
f
s
:
X
→
Y
can then
be constructed as follows:
f
s
(
x
)=
f
s
(
σ
n
···
σ
2
σ
1
)=
G
σ
n
(
···
G
σ
2
(
G
σ
1
(
s
))
···
)
Let's consider a toy example. For
n
=2, we can use the following PRBG
G
(
s
):
G
(00)
=
1001
G
(01)
=
0011
G
(10)
=
1110
G
(11)
=
0100
For
s
=10and
x
=01,wehave
