Cryptography Reference
In-Depth Information
information.) Therefore, we emphasize that the key K =( k 1 ,k 2 ,...,k B )canbe
used to authenticate arbitrary-length messages.
Remark 2. Clearly, as will be formally proven in Section 5, the bound on the
probability of successful forgery is dependent on the security parameter N .
Depending on application, one might require lower bounds on probability of
successful forgery. A straightforward way is to increase the security parame-
ter to give lower probability of successful forgery. Another method is to hash
the same message multiple times with independent keys. This, however, will re-
quire a much longer key. A well-studied and more ecient method is to use the
Toeplitz-extension on the hash function [36, 39]. (See, e.g., [9] for a detailed use
of Toeplitz-extension to increase the security of MACs based on universal hash
functions.) Again, we omit describing this topic since it is out of the scope of
this work and refer interested readers to [9, 26, 36, 39] for more details.
Verification. Upon receiving a ciphertext-tag pair, ( c, τ ), the receiver calls the
corresponding decryption algorithm
D
to extract the plaintext M
||
r .Toverify
r , the receiver computes B− 1
the integrity of M
i =1 k i m i + k B r and authenticates
the message only if the computed value is congruent to the received τ modulo
p . Formally, the following integrity check must be satisfied for the message to be
authenticated:
||
B− 1
?
τ
k i m i + k B r
mod p.
(2)
i =1
Remark 3. We emphasize that the random nonce, r , requires no key manage-
ment. It is generated by the sender as the coin tosses of the signing algorithm
and delivered to the receiver via the ciphertext. In other words, it is not a shared
secret and it needs no synchronization.
5
Security Analysis
5.1 Security of the Proposed
E
-MAC
Assume that message M has been encrypted with any semantically secure en-
cryption scheme. For the rest of the paper, we will refer to M and τ as the
message and the tag generated at the transmitter's end, respectively; while M
and τ represent the message and the tag at the receiver's end, respectively. For
ease of notation, we will refer to the plaintext message as the concatenation of
M and r . The following lemmas are the main ingredient for the security of the
proposed
-MAC.
Lemma 1. Let m i and k i be the i th message block and i th key, respectively.
For a modified message block m i
E
mod p , the probability that k i m i
m i
k i m i
mod p is zero.
Lemma 1 is a direct consequence of the fact that, for a prime integer p ,
Z p is a
field.
 
Search WWH ::




Custom Search