Cryptography Reference
In-Depth Information
where
m
denotes the
th
block of
M
and
m
denotes the
th
block of
M
q
(note
that we write
m
instead of
m
q
for ease of notations since no distinction between
different messages is necessary). We will analyze equation (4) by considering the
following three cases:
M
and
M
q
differ by a single block,
M
and
M
q
differ by
two blocks, or
M
and
M
q
differ by more than two blocks.
1. Assume that only a single message block is different. Since addition is com-
mutative, assume without loss of generality that the first message block is
different; that is,
m
1
m
1
mod
p
. Since only the first message block is
different, equation (4) is equivalent to
k
1
m
1
≡ k
1
m
1
≡
mod
p.
(5)
Therefore, by Lemma 1, the probability of successful forgery given a single
block difference is
zero
.
2. Assume, without loss of generality, that the first two message blocks are
different; i.e.,
m
1
≡
m
1
mod
p
and
m
2
≡
m
1
+
δ
1
≡
m
2
+
δ
2
≡
m
2
mod
p
.
Then, equation (4) is equivalent to
k
1
δ
1
+
k
2
δ
2
≡
0mod
p.
(6)
Therefore, by Lemma 2, the probability of successful forgery given that ex-
actly two message blocks are different is at most 1
/
(
p
1).
3. Assume that more than two message blocks are different, i.e.,
m
i
≡
−
m
i
+
δ
i
≡
m
i
mod
p
;
∀
i
∈
I
⊆{
1
,
2
,
···
,B
}
;
|
I
|≥
3. Then, equation (4) is equivalent
to
k
i
δ
i
+
j∈I
j
=
i
k
j
δ
j
≡
0mod
p,
(7)
I
. Therefore, using Lemma 2 and the fact that
j∈I,j
=
i
k
j
δ
j
can be congruent to
zero
modulo
p
, the probability of success is at most 1
/p
.
(The difference between this case and the case of exactly two blocks is that,
for some
i
∈
even if the
δ
's are chosen to be nonzero integers,
j∈I,j
=
i
k
j
δ
j
can still be
congruent to zero modulo
p
.)
From the above three cases, the probability of successful forgery when the forged
tag has been outputted by the signing oracle is at most 1
/
(
p
−
1).
Unqueried tag
(
M
,τ
): Assume now that the tag
τ
is different than all the
recorded tags; that is,
τ
=
τ
q
for all
q
=1
, ··· ,q
s
.If
τ
is independent of the
recorded tags, then the probability of successful forgery is 1
/p
(using the fact
that the tag is uniformly distributed over
Z
p
). Assume, however, that
τ
is a
function of
τ
q
,fora
q
.Let
τ
≡
}
of the adversary's choice. (Note that,
γ
can be a function of any value recorded
by the adversary.) Then,
∈{
1
,
···
,q
s
}
τ
q
+
γ
mod
p
for some
γ
∈
Z
p
\{
0
(
K, M
,τ
) = 1 if and only if the following congruence
V
holds:
B
B
?
≡
k
m
τ
≡
τ
q
+
γ
≡
k
m
+
γ
mod
p,
(8)
=1
=1
Search WWH ::
Custom Search