Cryptography Reference
In-Depth Information
A
succeeds with probability at least Pr[
E
s
|
E
c
]. Let
E
p
be the event that the output
c
is
equal to one answer
c
i
from the oracle. If
E
p
occurs then
B
succeeds. We have proven
that
B
succeeds with probability
p
≥
Pr[
E
c
]
+
Pr[
E
s
∩
E
p
|
E
c
] Pr[
E
c
]
.
If neither
E
c
nor
E
p
occurs, then either
H
(
M
)
=
H
(
M
i
) for some
i
and
A
fails, or
1
H
(
M
) is new but the probability that
C
2
(
H
(
M
))
=
c
is equal to
N
−
d
. Therefore the
1
N
−
d
.Wehave
A
probability that
succeeds is at most
1
Pr[
E
s
∩
E
p
|
≤
E
c
]
−
N
d
hence
Pr[
E
s
|
Pr[
E
c
]
1
p
≥
Pr[
E
c
]
+
E
c
]
−
N
−
d
1
N
−
d
.
≥
p
s
−
thus
p
Lemma 3.5.
Given one uniformly distributed random permutation C on
M
of cardi-
nality N, let us define
H
(
x
1
,...,
x
)
=
C
(
···
C
(
C
(
x
1
)
⊕
x
2
)
⊕···⊕
x
−
1
)
⊕
x
.
We assume that the H function is implemented by an oracle, and we consider a non-
adaptive adversary who can send queries to the oracle with a limited total length of q:
if M
1
,...,
which are sent by the adversary to
the oracle, we assume that the total length is less than q. The purpose of the adversary
is to output two different sequences among all the queried one with the same H value.
The probability of success of any adversary is smaller than
M
d
denote the finite sequences on
M
q
(
q
+
1)
1
×
q
.
2
N
−
Proof.
Let
M
i
=
m
i
,
q
i
. We assume that the
M
i
's are pairwise different. We
let
E
denote the event that we have H(
M
i
)
m
i
,
1
||
...
||
=
H(
M
j
) for some
i
=
j
.
We define
U
i
,
j
=
C
(
···
C
(
C
(
m
i
,
1
)
+
m
i
,
2
)
···+
m
i
,
j
−
1
)
+
m
i
,
j
which is an intermediate value which is used to compute MAC(
M
i
). We call “collision”
an event
U
i
,
j
=
m
r
,
s
(it will
happen for any
C
) and nontrivial otherwise (it will depend on
C
). We let Coll denote
the event that a nontrivial collision occurs.
U
r
,
s
. This collision is trivial if
m
i
,
1
||
...
||
m
i
,
j
=
m
r
,
1
||
...
||
Search WWH ::
Custom Search