Cryptography Reference
In-Depth Information
F
from a random function by just outputting 0 if such a pair is found and 1
otherwise, because if
f
=
F
k
no collision can be found since
F
k
is a permutation.
However, this argument loses significance as
n
grows and, asymptotically, it
becomes irrelevant. Indeed, it can be shown that any pseudo-random permutation
is a pseudo-random function because the probability of finding a collision using a
polynomial number of queries is negligible. This is a consequence of the
PRP/PRF
Switching Lemma
(see[21, Lemma 3.17] for a proof) which says that the advantage
of a distinguisher trying to distinguish
F
from a pseudo-random function exceeds
that of a distinguisher trying to distinguish it from a pseudo-random permutation
by at most
q
2
n
+
1
, where
q
is the number of oracle queries. Since we
assume that
q
is a polynomial function of
n
, this function is negligible.
(
q
−
1
)/
Exercise 4.2
Modify Definition 4.2 so that the experiment outputs 1 if
b
=
b
(when
D
succeeds) and 0 otherwise, and define the advantage of
D
in this case.
In modern cryptography, block ciphers are usually modeled as efficient
pseudo-
random permutations
in the sense just mentioned where, for a 128-bit block length, a
key length between 128 and 256will typically be used. Block ciphers can also bemod-
eled as efficient
strong pseudo-random permutations
, a stronger concept obtained
by supposing that the distinguisher
D
not only has oracle access to the permutation
F
k
and to a random permutation
f
but also to their inverses
F
−
1
f
−
1
. This is moti-
vated by the fact that the use of a block cipher to build an encryption scheme usually
implies that honest parties must be able to compute
F
−
k
when running the decryption
algorithm. Pseudo-random permutations (or PRPs, for short) are also called
secure
PRPs under CPA
while strong pseudo-random permutations are
secure PRPs under
CCA
(see [90, Chap. 5]); note the analogy with the concepts of CPA security and
CCA security. We will indicate how to build CPA secure encryption schemes based
on block ciphers modeled as pseudo-random permutations and, of course, strong
pseudo-random permutations are useful in building CCA secure schemes. We insist,
however, that for reasons already explained, the naive encryption scheme obtained
from a strong pseudo-random permutation
F
by just letting the
F
k
be the encryption
functions is not CPA secure.
,
k
4.2 The Advanced Encryption Standard
Bearing in mind the previous considerations, modern block ciphers are built with the
aimof obtaining practically efficient pseudo-randompermutations that, as wewill see
in Theorem 4.1, serve to obtain CPA secure encryption schemes. One of the preferred
constructions for this purpose is the
substitution-permutation network
, which uses a
series of random-looking permutations to achieve diffusion and confusion as would
be expected from a pseudo-random permutation (see, for example, [109] for the
details). This is the approach used in the design of the
Advanced Encryption Standard
(AES), which is by far the most popular block cipher currently in use. However, it
