Cryptography Reference
In-Depth Information
is that, using the structure of neighboring hybrids, algorithm
D
can be easily
modified to distinguish the ensembles
{
U
n
+
1
}
n
∈N
.
The core of the argument is the way in which the distinguishability of neigh-
boring hybrids relates to the distinguishability of
G
1
(
U
n
) from
U
n
+
1
. As stated,
this relation stems from the structure of neighboring hybrids. Let us take a closer
look at the hybrids
H
n
and
H
k
+
1
{
G
1
(
U
n
)
}
n
∈N
and
for some 0
≤
k
≤
p
(
n
)
−
1. Another piece of
n
notation is useful: We let
suff
j
(
α
) denote the
j
-bit-long suffix of the string
α
,
where
j
≤|
α
|
. First observe (see justification later) that for every
x
∈{
0
,
1
}
n
,
pref
j
+
1
(
G
(
x
))
=
pref
1
(
G
1
(
x
))
·
pref
j
(
G
(
suff
n
(
G
1
(
x
))))
(3.7)
Thus (further justification follows),
·
pref
(
p
(
n
)
−
k
−
1)
+
1
G
U
(2
n
H
n
=
U
(1)
k
·
pref
1
G
1
U
(2
n
·
pref
p
(
n
)
−
k
−
1
G
suff
n
G
1
U
(2
n
≡
U
(1)
k
pref
p
(
n
)
−
(
k
+
1)
G
U
(2
n
U
(1)
k
+
1
H
k
+
1
n
=
·
·
pref
1
U
(3)
n
+
1
·
pref
p
(
n
)
−
k
−
1
G
suff
n
U
(3)
n
+
1
U
(1)
k
≡
Thus, the ability to distinguish
H
n
and
H
k
+
1
translates to the ability to distinguish
n
) from
U
(3)
G
1
(
U
(2)
n
+
1
, we uniformly select
r
k
n
+
1
: On input
α
∈{
0
,
1
}
∈{
0
,
1
}
and
n
apply the “hybrid distinguisher” to
r
·
pref
1
(
α
)
·
pref
p
(
n
)
−
k
−
1
(
G
(
suff
n
(
α
)))
.
Details follow.
First let us restate and further justify the equalities stated previously. We start
with notation capturing the operator mentioned a few lines earlier. For every
k
∈{
0
,
1
,...,
p
(
n
)
−
1
}
and
α
∈{
0
,
1
}
n
+
1
, let
)
def
p
(
n
)
−
k
f
p
(
n
)
−
k
(
α
=
pref
1
(
α
)
·
pref
p
(
n
)
−
k
−
1
(
G
(
suff
n
(
α
)))
∈{
0
,
1
}
(3.8)
Claim 3.3.3.1 (G
1
(U
n
) and U
n
+
1
versus H
n
and H
k
+
1
):
n
is distributed identically to
U
(1)
k
1.
H
n
f
p
(
n
)
−
k
(
G
1
(
U
(2)
·
)).
n
is distributed identically to
U
(1)
k
f
p
(
n
)
−
k
(
U
(3)
2.
H
k
+
1
n
·
n
+
1
).
Proof:
Consider
any
x
∈{
0
,
1
}
n
,
and
let
σ
=
pref
1
(
G
1
(
x
))
and
y
=
suff
n
(
G
1
(
x
))
(i.e.,
σ
y
=
G
1
(
x
)).
Then,
by
construction
of
G
,wehave
G
(
x
)
=
σ
·
pref
p
(
n
)
−
1
(
G
(
y
)). This justifies Eq. (3.7); that is,
pref
j
+
1
(
G
(
x
))
=
pref
1
(
G
1
(
x
))
·
pref
j
(
G
(
suff
n
(
G
1
(
x
)))) for every
j
≥
0. We now establish the
two parts of the claim:
1.
Combining the definition of
H
n
and Eq. (3.7), we have
pref
(
p
(
n
)
−
k
−
1)
+
1
G
U
(2
n
H
n
=
U
(1)
k
·
pref
1
G
1
U
(2
n
·
pref
p
(
n
)
−
k
−
1
G
suff
n
G
1
U
(2
n
U
(1)
k
=
·
f
p
(
n
)
−
k
G
1
U
(2
n
U
(1)
k
=
·
which establishes the first part.
