Cryptography Reference
In-Depth Information
3.7.
∗
Pseudorandom Permutations
In this section we present definitions and constructions for pseudorandom permuta-
tions. Clearly, pseudorandom permutations (over huge domains) can be used instead of
pseudorandom functions in any efficient application, yet pseudorandom permutations
offer the extra advantage of having unique pre-images. This extra advantage can some-
times be useful, but less than what one might expect (e.g., it is not used in the rest of
this topic, not even in the chapter on encryption schemes, for reasons explained there).
We show how to construct pseudorandom permutations using pseudorandom
functions as building blocks, in a manner identical to the high-level structure of the
DES. Hence, the proof presented in this section can be viewed as supporting the
DES's methodology of converting “random-looking” functions into “random-looking”
permutations.
10
3.7.1. Definitions
We start with the definition of pseudorandom permutations. Loosely speaking, a pseudo-
random ensemble of permutations is defined analogously to a pseudorandom ensemble
of functions. Namely:
Definition 3.7.1 (Permutation Ensembles):
A
permutation ensemble
is a se-
quence P
P
n
}
n
∈N
of random variables such that the random variable P
n
as-
sumes values in the set of permutations mapping n-bit-long strings to n-bit-long
strings. The
uniform permutation ensemble,
denoted K
={
K
n
}
n
∈N
, has K
n
uni-
formly distributed over the set of all permutations mapping n-bit-long strings to
n-bit-long strings.
={
Every permutation ensemble is a function ensemble. Hence the definition of an
efficiently computable
permutation ensemble is obvious (i.e., it is derived from the
definition of an efficiently computable function ensemble). Pseudorandom permuta-
tions are defined as computationally indistinguishable from the uniform
permutation
ensemble.
Definition 3.7.2 (Pseudorandom Permutation Ensembles):
A permutation
ensemble P
P
n
}
n
∈N
is called
pseudorandom
if for every probabilistic poly-
nomial-time oracle machine M , every polynomial p
(
={
·
)
, and all sufficiently large
n's,
Pr
1
<
M
P
n
(1
n
)
1
−
Pr
M
K
n
(1
n
)
1
p
(
n
)
=
=
where K
={
K
n
}
n
∈N
is the uniform permutation ensemble.
The fact that
P
is a pseudorandom permutation ensemble, rather than just a pseu-
dorandom function ensemble, cannot be detected in poly(
n
) time by an observer given
10
The fact that in the DES this methodology is applied to functions that are
NOT
“random-looking” is not of
concern here.
