Cryptography Reference
In-Depth Information
oracle access to
P
n
. This fact stems from the observation that the uniform permutation
ensemble is polynomial-time-indistinguishable from the uniform function ensemble.
Namely:
Proposition 3.7.3:
The uniform permutation ensemble
(
i.e., K
={
K
n
}
n
∈N
)
con-
stitutes a pseudorandom function ensemble.
Proof Sketch:
Recall that
{
H
n
}
n
∈N
denotes the uniform function ensemble. The
probability that when given access to oracle
H
n
a machine will detect a collision
in the oracle function is bounded by
t
2
2
−
n
, where
t
denotes the number of
queries made by the machine. Conditioned on not finding such a collision, the
answers of
H
n
are indistinguishable from those of
K
n
. Finally, using the fact
that a polynomial-time machine can ask at most polynomially many queries, the
proposition follows.
·
Hence, the use of pseudorandom permutations instead of pseudorandom functions has
reasons beyond the question of whether or not a computationally restricted observer
can detect the difference. Typically, the reason is that one wants to be guaranteed
of the
uniqueness
of pre-images. A natural strengthening of this requirement is that
given the description of the permutation,
the
(unique)
pre-image can be efficiently
found
.
Definition 3.7.4 (Efficiently Computable and Invertible Permutation Ensem-
bles):
A permutation ensemble P
P
n
}
n
∈N
is called
efficiently computable
and invertible
if the following three conditions hold:
={
1.
Efficient indexing:
There exists a probabilistic polynomial-time algorithm I and a
mapping from strings to permutation,
(
I
(1
n
))
and P
n
are identically
φ
, such that
φ
distributed.
2.
Efficient evaluation:
There exists a probabilistic polynomial-time algorithm V
such that V
(
i
def
=
φ
(
i
)
.
3.
Efficient inversion:
There exists a probabilistic polynomial-time algorithm N such
that N
(
i
,
x
)
=
f
i
(
x
)
, where
(
as in Definition 3.6.3
)
f
i
f
−
1
i
,
x
)
=
(
x
)(
i.e., f
i
(
N
(
i
,
x
))
=
x
)
.
Items 1 and 2 are guaranteed by the definition of an efficiently computable permutation
ensemble. The additional requirement is stated in Item 3. In some settings it makes sense
to augment the definition of a pseudorandom ensemble by requiring that the ensemble
cannot be distinguished from the uniform one even when the observer gets access to
two oracles: one for the permutation and the other for its inverse. Thus, we consider
augmented oracle machines that can make queries to two oracles; the two-oracle model
can be emulated by the standard (single) oracle model by combining the two oracles
f
1
and
f
2
into one oracle
f
defined by
f
(
i
,
q
)
=
f
i
(
q
).
Definition 3.7.5 (Strong Pseudorandom Permutations):
A permutation ensem-
ble P
={
P
n
}
n
∈N
is called
strongly pseudorandom
if for every probabilistic
165
