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