Cryptography Reference
In-Depth Information
$%&
Figure 2.6
A PRBG.
Note that the pseudorandom bit sequence a PRBG outputs may be of infinite
length (i.e.,
l
=
). Also note that in contrast to a random bit generator, a PRBG
represents a deterministic algorithm (i.e., an algorithm that can be implemented in
a deterministic way). This suggests that a PRBG is implemented as a finite state
machine and that the sequence of generated bits must be cyclic (with a potentially
very large cycle). This is why we cannot require that the bits in a pseudorandom
sequence are truly random, we can only require that they appear to be so (for a
computationally bounded adversary). Again, many statistical tests can be used to
verify the randomness properties of a binary sequence. Note, however, that passing
all of these tests is a necessary but usually not sufficient condition for a binary
sequence to be securely used for cryptographic applications.
PRBGs have many applications in cryptography. Examples include additive
stream ciphers, as well as cryptographic key generation and expansion. In fact, the
title of [1] suggests that the notion of pseudorandomness and (modern) cryptography
are closely related and deeply intertwined. The notion of a PRBG and some possible
constructions for cryptographically secure PRBGs are further addressed in Chapter
12.
∞
2.2.4
PRFs
Contrary to PRBGs, PRFs do not generate an output that meets specific (random-
ness) requirements. Instead, PRFs try to model the input-output behavior of a ran-
dom function (i.e., a function
f
:
X
Y
that is randomly chosen from the set
of all mappings from domain
X
to range
Y
). Random functions are also known as
random oracles. For input value
x
→
∈
X
, a PRF computes an arbitrary output value
y
=
f
(
x
)
Y
. The only requirement is that the same input value
x
must
always be mapped to the same output value
y
. PRBGs and (families of ) PRFs are
closely related to each other in the sense that a PRF family can be used to construct
∈
f
(
X
)
⊆
