eprint.iacr.org will be offline for approximately an hour for routine maintenance again at 10pm UTC on Wednesday, April 17.

Paper 2011/442

Another Look at Tightness

Sanjit Chatterjee, Alfred Menezes, and Palash Sarkar


We examine a natural, but non-tight, reductionist security proof for deterministic message authentication code (MAC) schemes in the multi-user setting. If security parameters for the MAC scheme are selected without accounting for the non-tightness in the reduction, then the MAC scheme is shown to provide a level of security that is less than desirable in the multi-user setting. We find similar deficiencies in the security assurances provided by non-tight proofs when we analyze some protocols in the literature including ones for network authentication and aggregate MACs. Our observations call into question the practical value of non-tight reductionist security proofs. We also exhibit attacks on authenticated encryption and disk encryption schemes in the multi-user setting.

Note: Removed some inaccuracies in the description and analysis of Attack 1.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. Also available at http://anotherlook.ca
Contact author(s)
ajmeneze @ uwaterloo ca
2013-04-01: last of 7 revisions
2011-08-15: received
See all versions
Short URL
Creative Commons Attribution


      author = {Sanjit Chatterjee and Alfred Menezes and Palash Sarkar},
      title = {Another Look at Tightness},
      howpublished = {Cryptology ePrint Archive, Paper 2011/442},
      year = {2011},
      note = {\url{https://eprint.iacr.org/2011/442}},
      url = {https://eprint.iacr.org/2011/442}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.