Cryptography Reference
In-Depth Information
polynomial-time oracle machine M , every polynomial p
(
·
)
, and all sufficiently
large n's,
Pr
1
<
1
p
(
n
)
where M
f
,
g
denotes the execution of machine M when given access to the oracles
f and g.
M
P
n
,
P
−
1
1
−
Pr
M
K
n
,
K
−
1
(1
n
)
(1
n
)
=
=
n
n
3.7.2. Construction
The construction of pseudorandom permutations uses pseudorandom functions as build-
ing blocks, in a manner identical to the high-level structure of the DES (see Figure 3.6).
Namely:
n
n
. For every x
,
y
∈{
0
,
1
}
n
, we define
Construction 3.7.6:
Let f
:
{
0
,
1
}
→{
0
,
1
}
DES
f
(
x
,
y
)
def
=
(
y
,
x
⊕
f
(
y
))
where x
y denotes the bit-by-bit XOR of the binary strings x and y. Likewise,
for f
1
,...,
⊕
f
t
:
{
0
,
1
}
n
→{
0
,
1
}
n
, we define
y
)
def
DES
f
t
,...,
f
1
(
x
,
=
DES
f
t
,...,
f
2
(DES
f
1
(
x
,
y
))
For every function ensemble F
={
F
n
}
n
∈N
and every function t
:
N→N
, we de-
fine the function ensemble
DES
t
(
n
)
F
n
}
n
∈N
by letting
DES
t
(
n
)
def
=
,...,
F
(1
n
, where
t
=
t
(
n
)
and the F
(
i
n
's are independent copies of the random variable F
n
.
{
DES
F
(
t
)
n
F
n
)
, and
DES
t
(
n
)
Theorem 3.7.7:
Let F
n
,t
(
F
n
be as in Construction 3.7.6. Suppose
that
{
F
n
}
n
∈N
is efficiently computable and that on input n one can compute t
(
n
)
in
poly(
n
)
time. Then for every polynomial-time-computable function t
(
·
)
, the
ensemble
{
DES
t
(
n
)
·
}
n
∈N
is an efficiently computable and invertible permutation
F
n
y
x
f
+
y
Figure 3.6:
The high-level structure of the DES.
x+f(y)
