Cryptography Reference
In-Depth Information
where m denotes the th block of M and m denotes the th block of M q . Bellow
we analyze equation (8) by considering two cases: M and M q differ by a single
block, or M and M q differ by more than one block.
1. Without loss of generality, assume that M and M q
differ in the first block
only. That is m 1
m 1 mod p and m i
m 1 + δ
m i
mod p for all
i =2 ,
···
,B . Then, equation (8) is equivalent to
k 1 δ
γ
mod p.
(9)
1).
2. Assume now that M and M q differ by more than one block. That is, m i
m i + δ i
Therefore, by Lemma 2, the probability of success is at most 1 / ( p
= m i mod p ;
i
I
⊆{
1 , 2 ,
···
,B
}
;
|
I
|≥
2. Then, equation (8) is
equivalent to
k i δ i ≡ γ
mod p.
(10)
i∈I
By Lemma 2 and the fact that i∈I k i δ i can be congruent to zero modulo
p , the probability of success is at most 1 /p .
From the above two cases, the probability of successful forgery when the forged
tag has not been outputted by the signing oracle is at most 1 / ( p
1).
Therefore, given that
A
has made at least one signing query,
A
's probability
of successful forgery for each verify query is at most 1 / ( p
1).
Remark 5. Observe that the case of queried tag implies that the used hash family
is (
1
p−
1 )-AU. Similarly, the case of unqueried tag implies that the used hash
family is (
1
p− 1 )-A Δ U.
Observe further that the proposed E -MAC is strongly unforgeable under cho-
sen message attacks (SUF-CMA). Recall that SUF-CMA requires that it be
computationally infeasible for the adversary to find a new message-tag pair af-
ter chosen-message attacks even if the message is not new, as long as the tag
has not been attached to the message by a legitimate user [5]. To see this, let
( M, τ ) be a valid message tag pair. Assume that the adversary is attempting to
authenticate the same message with a different tag τ .Forthe( M, τ )pairto
be authenticated, i k i m i + k B r
mod p must be equal to τ .Thatis,given τ ,
r must be set to k B ( τ i k i m i )mod p for the tag to be authenticated. By
Theorem 1, however, the adversary cannot expose the
-MAC's key. Therefore,
Theorem 2 holds whether or not the message is new, as long as the tag has not
been attached to the message by the signing oracle.
E
5.2 Security of the E & A Composition
In [5], Bellare and Namprempre defined two notions of integrity in authenticated
encryption schemes, integrity of plaintexts (INT-PTXT) and integrity of cipher-
texts (INT-CTXT). INT-PTXT implies that it is computationally infeasible for
an adversary to produce a ciphertext decrypting to a message which the sender
 
Search WWH ::




Custom Search