The Power of Verification Queries in Message Authentication and Authenticated Encryption

Mihir Bellare; Oded Goldreich; Anton Mityagin

Paper 2004/309

The Power of Verification Queries in Message Authentication and Authenticated Encryption

Mihir Bellare, Oded Goldreich, and Anton Mityagin

Abstract

This paper points out that, contrary to popular belief, allowing a message authentication adversary multiple verification attempts towards forgery is NOT equivalent to allowing it a single one, so that the notion of security that most message authentication schemes are proven to meet does not guarantee their security in practice. We then show, however, that the equivalence does hold for STRONG unforgeability. Based on this we recover security of popular classes of message authentication schemes such as MACs (including HMAC and PRF-based MACs) and CW-schemes. Furthermore, in many cases we do so with a TIGHT security reduction, so that in the end the news we bring is surprisingly positive given the initial negative result. Finally, we show analogous results for authenticated encryption.

Metadata

Available format(s): PDF PS
Category: Secret-key cryptography
Publication info: Published elsewhere. Unknown where it was published
Keywords: message authentication authenticated encryption MAC PRF
Contact author(s): mihir @ cs ucsd edu
History: 2004-11-18: revised; 2004-11-16: received; See all versions
Short URL: https://ia.cr/2004/309
License: CC BY

BibTeX

@misc{cryptoeprint:2004/309,
      author = {Mihir Bellare and Oded Goldreich and Anton Mityagin},
      title = {The Power of Verification Queries in Message Authentication and Authenticated Encryption},
      howpublished = {Cryptology ePrint Archive, Paper 2004/309},
      year = {2004},
      note = {\url{https://eprint.iacr.org/2004/309}},
      url = {https://eprint.iacr.org/2004/309}
}