Paper 2011/442

Another Look at Tightness

Sanjit Chatterjee, Alfred Menezes, and Palash Sarkar

Abstract

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.

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

BibTeX

@misc{cryptoeprint:2011/442,
      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.