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