Improving the security of MACs via randomized message preprocessing

Yevgeniy Dodis, Krzysztof Pietrzak

Research output: Chapter in Book/Report/Conference proceedingConference contribution


"Hash then encrypt" is an approach to message authentication, where first the message is hashed down using an ε-universal hash function, and then the resulting k-bit value is encrypted, say with a block-cipher. The security of this scheme is proportional to εq2, where q is the number of MACs the adversary can request. As ε is at least 2-k, the best one can hope for is O(q2 /2k) security. Unfortunately, such small ε is not achieved by simple hash functions used in practice, such as the polynomial evaluation or the Merkle-Damgård construction, where ε grows with the message length L. The main insight of this work comes from the fact that, by using randomized message preprocessing via a short random salt p (which must then be sent as part of the authentication tag), we can use the "hash then encrypt" paradigm with suboptimal "practical" ε-universal hash functions, and still improve its exact security to optimal O(q2/2k). Specifically, by using at most an 0(logL)-bit salt p, one can always regain the optimal exact security O(q2/2k), even in situations where ε grows polynomially with L. We also give very simple preprocessing maps for popular "suboptimal" hash functions, namely polynomial evaluation and the Merkle-Damgård construction. Our results come from a general extension of the classical Carter-Wegman paradigm, which we believe is of independent interest. On a high level, it shows that public randomization allows one to use the potentially much smaller "average-case" collision probability in place of the "worst-case" collision probability ε.

Original languageEnglish (US)
Title of host publicationFast Software Encryption - 14th International Workshop, FSE 2007
PublisherSpringer Verlag
Number of pages20
ISBN (Print)354074617X, 9783540746171
StatePublished - 2007
Event14th International Workshop on Fast Software Encryption, FSE 2007 - Luxembourg, Luxembourg
Duration: Mar 26 2007Mar 28 2007

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume4593 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other14th International Workshop on Fast Software Encryption, FSE 2007

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Improving the security of MACs via randomized message preprocessing'. Together they form a unique fingerprint.

Cite this