Cryptography Reference
In-Depth Information
We call “inversion” the event Inv that
C
(
U
i
,
j
)
=
0 for some
i
,
j
.
The
E
event is clearly included in Inv
∪
Coll: if
U
i
,
q
i
=
U
r
,
q
r
, then either
m
i
,
q
i
=
m
r
,
q
r
and it is a nontrivial collision, or it reduces to
U
i
,
q
i
−
1
=
U
r
,
q
r
−
1
and we can iterate.
Thus Pr[
E
]
≤
Pr[Inv]
+
Pr[Coll].
In order to determine an upper bound on Pr[Inv], we can transform the collision
attack against MAC into an inversion attack against
C
: we say that it succeeds whenever
C
(
U
i
,
j
)
0 for some
i
and
j
. Clearly Pr[Inv] is the probability of success of this
attack. But the probability that any adaptive attack against
C
finds a preimage of 0
after
q
queries is less than
q
=
N
−
q
: once the attack has submitted
i
queries,
C
is bound
to
i
input/output pairs, but since
C
is uniformly distributed, the encryption of any
new block is uniformly distributed among all other possible outputs, thus it is the
zero block with probability
1
N
−
i
1
N
−
q
which is less than
when
i
is less than
q
. Thus
q
N
−
q
.
Pr[Inv]
≤
The remaining part of the proof is devoted to finding the upper bound of
Pr[Coll].
We let
U
be the set of all
U
i
,
j
-indices, which means the set of all (
i
,
j
) such that
1
≤
i
≤
d
and 1
≤
j
≤
q
i
.For
A
⊆
U
we let
c
(
A
)be
={
,
∃
,
∈
=
≤
}
.
c
(
A
)
(
i
j
);
(
r
s
)
Ai
r
and
j
s
Thus
c
(
A
) is the set of the indices of all
U
i
,
j
which are required in order to compute
all
U
r
,
s
values for (
r
A
. We define an ordering on the set 2
U
of all subsets of
,
s
)
∈
U
by
A
≤
B
⇐⇒
A
⊆
c
(
B
)
.
A
is less than
B
if all indices in
A
are required to compute the indices in
B
.
We let
I
be the set of all pairs of indices of potential nontrivial collisions
U
i
,
j
=
U
r
,
s
, namely the set of all pairs
{
(
i
,
j
)
,
(
r
,
s
)
}
of
U
-elements such that
m
i
,
1
||
...
||
m
i
,
j
=
m
r
,
1
||
...
||
m
r
,
s
.For
{
(
i
,
j
)
,
(
r
,
s
)
}∈
I
we let Coll
i
,
j
,
r
,
s
be the event
of the collision
U
i
,
j
=
I
),
and we let MinColl
i
,
j
,
r
,
s
be the complementary, in Coll
i
,
j
,
r
,
s
, of the union of all
Coll
i
,
j
,
r
,
s
U
r
,
s
(which is necessarily nontrivial since
{
(
i
,
j
)
,
(
r
,
s
)
}∈
{
(
i
,
j
)
,
(
r
,
s
)
}∈
{
(
i
,
j
)
,
(
r
,
s
)
}
<
{
,
,
,
}
for
I
and
(
i
j
)
(
r
s
)
:wehavea
collision
U
i
,
j
=
U
r
,
s
. We easily no-
tice that the nontrivial collision event Coll is the union of all nontrivial minimal
collisions:
U
r
,
s
with no lower nontrivial collision
U
i
,
j
=
=
MinColl
i
,
j
,
r
,
s
.
Coll
{
(
i
,
j
)
,
(
r
,
s
)
}∈
I
Search WWH ::
Custom Search