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