Cryptography Reference
In-Depth Information
ensemble. Furthermore, if F
={
F
n
}
n
∈N
is a pseudorandom function ensemble,
then the ensemble
{
DES
F
n
}
n
∈N
is pseudorandom and the ensemble
{
DES
F
n
}
n
∈N
is
strongly pseudorandom.
DES
t
(
n
)
F
n
}
n
∈N
is efficiently computable. The fact that it is a per-
mutation ensemble, and furthermore one with an efficient inverting algorithm, follows
from the observation that DES
zero
,
f
,
zero
is the inverse of DES
f
, where zero(
z
)
def
Clearly, the ensemble
{
0
|
z
|
for
=
n
. That is, for every
x
n
, DES
zero
(
x
all
z
∈{
0
,
1
}
,
y
∈{
0
,
1
}
,
y
)
=
(
y
,
x
), and
DES
zero
,
f
,
zero
(DES
f
(
x
,
y
))
=
DES
zero
,
f
,
zero
(
y
,
x
⊕
f
(
y
))
=
DES
zero
,
f
(
x
⊕
f
(
y
)
,
y
)
=
DES
zero
(
y
,
(
x
⊕
f
(
y
))
⊕
f
(
y
))
=
(
x
,
y
)
To prove the pseudorandomness of
{
DES
F
n
}
n
∈N
(resp., strong pseudorandomness of
{
DES
F
n
}
n
∈N
) it suffices to prove the pseudorandomness of
{
DES
3
H
n
}
n
∈N
(resp., strong
pseudorandomness of
{
DES
4
H
n
}
n
∈N
). The reason is that if, say,
{
DES
3
H
n
}
n
∈N
is pseudo-
random, while
{
DES
F
n
}
n
∈N
is not, then one can derive a contradiction to the pseudo-
randomness of the function ensemble
F
(i.e., distinguish
F
from the uniform function
ensemble
H
; see Exercise 35). Hence, Theorem 3.7.7 follows from Proposition 3.7.8.
DES
3
H
n
}
n
∈N
DES
4
H
n
}
n
∈N
Proposition
3.7.8:
{
is
pseudorandom,
whereas
{
is
strongly pseudorandom.
DES
3
H
n
}
n
∈N
Proof Sketch:
We start by proving that
{
is pseudorandom. Let
def
={
DES
3
H
n
}
n
∈N
, and let
K
2
n
be the random variable uniformly distributed
over all possible permutations acting on
P
2
n
{
0
,
1
}
2
n
. We prove that for every oracle
machine
M
that on input 1
n
asks at most
m
queries, it holds that
Pr
M
P
2
n
(1
n
)
=
1
−
Pr
M
K
2
n
(1
n
)
=
1
≤
2
m
2
2
n
(3.17)
n
, be a random variable representing the
i
th query of
M
when given access to oracle
P
2
n
. Recall that
P
2
n
=
Let
q
i
=
(
L
i
,
R
i
), with
|
L
i
|=|
R
i
|=
n
,
where the
H
(
j
n
's are three independent random variables, each uniformly dis-
tributed over the functions acting on
DES
H
(3)
n
,
H
(2)
n
,
H
(1)
def
=
n
. Let
R
k
+
1
i
H
(
k
+
1)
n
{
0
,
1
}
L
i
⊕
(
R
i
) and
def
=
R
i
L
k
+
1
for
k
=
,
,
2. That is,
L
k
+
1
i
0
1
i
R
k
+
i
R
i
,
H
(
k
+
1
n
R
i
L
i
⊕
,
=
We assume, without loss of generality, that
M
never asks the same query twice.
We define a random variable
ζ
m
representing the event that there exist
i
<
j
≤
m
and
k
∈{
1
,
2
}
such that
R
i
=
R
j
(namely, on input 1
n
and access to oracle
P
2
n
,
two of the
m
first queries of
M
satisfy the relation
R
i
=
R
j
). We use the following
two claims.
