Cryptography Reference
In-Depth Information
Lemma 2.
Let
k
1
and
k
2
be two secret keys in the proposed
E
-MAC. The prob-
ability to choose two nonzero integers
δ
1
and
δ
2
in
Z
p
such that
k
1
δ
1
≡
k
2
δ
2
mod
p
is at most
1
/
(
p
−
1)
.
Proof.
Fix a
δ
1
∈
Z
p
. Since every nonzero element in
Z
p
is invertible, the result-
Z
p
. Similarly, the resulting
ing (
k
1
δ
1
mod
p
) will be uniformly distributed over
Z
p
.Since
k
1
and
k
2
are assumed to
(
k
2
δ
2
mod
p
) is uniformly distributed over
be secret, the probability that
k
1
δ
1
≡
k
2
δ
2
mod
p
is 1
/
(
p
−
1), and the lemma
follows.
Lemma 3.
Authentication tags are statistically independent of their correspond-
ing messages, and different authentication tags are mutually independent.
The proof of Lemma 3 is provided in Appendix A. Now we can proceed with
the proofs of the main claims of the proposed
-MAC. Recall that applying a
cryptographic function to the compressed image is an essential operation for
the security of standard universal hash functions based MACs. Without such
a cryptographic operation, the key of the universal hash function can be ex-
posed (by chosen message attacks, for instance). We now formally prove two
important claims about
E
-MACs. Namely, the semantic security of the used en-
cryption algorithm suces to protect the key of the proposed
E
-MAC, and tags
do not reveal any information about the plaintext that is not revealed by the
corresponding ciphertext.
E
Theorem 1.
An adversary able to extract any information about the proposed
E
-MAC's secret key, or extract any information about the plaintext from authen-
tication tags is able to break the semantic security of the underlying encryption
algorithm.
Proof.
By Lemma 3, each tag is independent of its corresponding message and
the secret key. Therefore, by only observing a single tag, the adversary can-
not reveal any information about the authenticated message or the secret key.
Furthermore, also by Lemma 3, different authentication tags are mutually inde-
pendent. Therefore, the observation of multiple tags gives the adversary no extra
information than what a single tag gives individually. This holds as long as the
coin tosses, the
r
's, remain secret. The transmitted
r
's, however, are generated
internally and encrypted with the semantically secure algorithm
E
. Therefore, no
information about the proposed
-MAC's key nor the authenticated messages
can be exposed, unless the adversary can extract secret information about the
r
's, which can be done only by breaking the semantic security of the encryption
algorithm.
E
Remark 4.
In addition to its important statement regarding the secrecy of trans-
mitted messages, Theorem 1 presents an important statement regarding the se-
crecy of the nonce
r
. Clearly, if some
r
's are revealed, partial key information
can be exposed. Other than attacking the system in a non-cryptographic way,
Theorem 1 states that the only way to expose secrete information about the
r
's
is by breaking the semantic security of the encryption algorithm. That is, from
Search WWH ::
Custom Search