Cryptography Reference
In-Depth Information
Proof of Theorem 1.
For 1
≤
i
≤
q
,let(
t
i
,k
i
,w
i
x
i
,y
i
z
i
) be a tuple such that
E
(
k
i
,w
i
obtained by the
i
-th query.
t
i
represents the
type of the
i
-th query: encryption (
e
) or decryption (
d
). Let
G
1
,G
2
,...,G
q
be
a sequence of directed graphs such that
G
i
=(
V
i
,L
i
), where
-
V
1
=
x
i
)=
y
i
z
i
and
t
i
∈{
e
,
d
}
{
k
1
x
1
,y
1
z
1
}
,
L
1
=
L
i
∪{
(
k
1
x
1
,y
1
z
1
)
}
,and
-
V
i
=
V
i−
1
∪{
k
i
x
i
,y
i
z
i
}
,
L
i
=
L
i−
1
∪{
(
k
i
x
i
,y
i
z
i
)
}
for 2
≤
i
≤
q
.
Each edge (
k
i
x
i
,w
i
),
where
h
is the Lesamnta-LW compression funcuion specified in Sect. 2.2.
Suppose that the adversary
A
first finds a collision of Lesamnta-LW with the
i
-th query. Then, there must be a path in
G
i
from
IV
0
IV
1
to some colliding
output, which does not exist in
G
1
,...,G
i−
1
. This path also contains the nodes
k
i
x
i
,y
i
z
i
) is labeled by (
t
i
,w
i
). Notice that
y
i
z
i
=
h
(
k
i
z
i
, and the edge (
t
i
,w
i
).
If
t
i
=
e
,thatis,the
i
-th query is an encryption query, then there must be
an event such that
y
i
x
i
and
y
i
z
i
∈{
y
j
z
j
|
1
≤
j
≤
i
−
1
}∪{
k
j
x
j
|
1
≤
j
≤
i
−
1
}∪
{
IV
0
IV
1
}
.If
t
i
=
d
, then there must be an event such that
k
i
x
i
∈{
y
j
z
j
|
1
≤
j
≤
.
For the case where
t
i
i
−
1
}∪{
IV
0
IV
1
}
=
d
and
k
i
x
i
∈{
y
j
z
j
|
1
≤
j
≤
i
−
1
}
,letuslook
(
t
j
1
,M
j
1
)
(
t
j
2
,M
j
2
)
into the new path in
G
i
mentioned above. Let
IV
0
IV
1
−→
v
j
1
−→
(
t
j
l
−
1
,M
j
l
−
1
)
(
t
j
l
,M
j
l
)
···
−→
v
j
l
−
1
−→
v
j
l
be the prefix of the path, where
v
j
l
−
1
=
k
i
x
i
,
(
t
j
l
,M
j
l
)=(
d
,w
i
)and
v
j
l
=
y
i
z
i
.Westartfrom
v
j
l
and go back toward
IV
0
IV
1
until we first find an edge (
e
,M
j
k
)orreachthenode
IV
0
IV
1
without
finding such an edge. Suppose that we reach
IV
0
IV
1
. Then, it implies that
there is an event such that
t
i
=
d
and
k
i
x
i
=
IV
0
IV
1
for some
i
such that
i
<i
. On the other hand, suppose that we find an edge (
e
,M
j
k
). Then, it
implies that there is an event such that
t
i
=
e
and
y
i
≤
1
j<i
}
z
i
∈{
k
j
x
j
|
≤
1
for some
i
such that 1
<i
<i
,oraneventsuchthat
t
i
=
d
and
k
i
x
i
∈
j<i
∧
for some
i
such that 1
<i
≤
{
i
.
From the discussions above, if
A
finds a collision with at most
q
queries, then
it implies that there must be at least one of the following events for some
i
such
that 1
y
j
z
j
|
1
≤
t
j
=
e
}
≤
i
≤
q
:
Ea
i
t
i
=
e
and
y
i
z
i
=
IV
0
IV
1
,
Eb
i
t
i
=
e
and
y
i
z
i
∈{
y
j
z
j
|
1
≤
j
≤
i
−
1
}∪{
k
j
x
j
|
1
≤
j
≤
i
−
1
}
,
t
i
=
d
and
k
i
x
i
=
IV
0
IV
1
,
Ec
i
Ed
i
t
i
=
d
and
k
i
x
i
∈{
y
j
z
j
|
1
≤
j<i
∧
t
j
=
e
}
.
It is easy to see that
2
n
1
2(
i −
1)
2
2
n
Pr[
Ea
i
]
≤
,
Pr[
Eb
i
]
≤
,
Pr[
Ec
i
]
≤
.
2
2
n
−
(
i
−
1)
−
(
i
−
1)
2
2
n
−
(
i
−
1)
For
Ed
i
, the probability of multicollision on
y
j
should be taken into consideration.
From Corollary 1, for 1
2
n−
2
,
≤
q
≤
1)2
n
(
n
−
1
Pr[
Ed
i
]
≤
1)
+
.
2
2
n
−
(
i
−
n
!
·
2
n
Search WWH ::
Custom Search