Cryptography Reference
In-Depth Information
we mean by saying that
F
is secure. Intuitively, we would say that
F
is a secure PRF
family if its prf-advantage is negligible for all practically relevant input parameters,
and we would then say that input parameters are practically relevant if they refer to
resources that are polynomially bound. The notion of a secure PRF can be defined
along these lines. In fact, this definitional framework is frequently used in modern
cryptography. It basically consists of the following steps:
•
First, one defines experiments that involve an adversary.
•
Second, one specifies an advantage function associated to an adversary. For
a specific adversary, the advantage function returns the probability that he or
she “breaks” the scheme (i.e., provides a correct answer).
•
Third, one specifies an advantage function associated to the cryptographic sys-
tem in question. This function takes input resource parameters and returns the
maximum probability of “breaking” the system if the adversary is restricted
to the specified resource parameters.
If the advantage function returns a sufficiently small maximum probability for
all reasonable resource parameters, then one considers the cryptographic system to
be secure for practical purposes.
13.2
CONSTRUCTIONS
As mentioned earlier, a PRF family can be used to construct a PRBG, and a PRBG
can be used to construct a PRF family. Let us overview and briefly discuss these
constructions.
13.2.1
PRF-Based PRBG
If we ask whether it is possible to construct a PRBG using a PRF family, then we
can answer in the affirmative. In fact, the corresponding construction is fairly trivial.
Let
F
be a PRF family with key space
K
. If we randomly choose
k
∈
R
K
,fixthe
PRF
f
k
, iteratively apply
f
k
to a counter value (starting, for example, with zero),
then we generate the following sequence of values:
f
k
(0)
f
k
(1)
f
k
(2)
