Paper 2012/059

Message Authentication, Revisited

Yevgeniy Dodis, Eike Kiltz, Krzysztof Pietrzak, and Daniel Wichs


Traditionally, symmetric-key message authentication codes (MACs) are easily built from pseudorandom functions (PRFs). In this work we propose a wide variety of other approaches to building efficient MACs, without going through a PRF first. In particular, unlike deterministic PRF-based MACs, where each message has a unique valid tag, we give a number of probabilistic MAC constructions from various other primitives/assumptions. Our main results are summarized as follows: * We show several new probabilistic MAC constructions from a variety of general assumptions, including CCA-secure encryption, Hash Proof Systems and key-homomorphic weak PRFs. By instantiating these frameworks under concrete number theoretic assumptions, we get several schemes which are more efficient than just using a state-of-the-art PRF instantiation under the corresponding assumption. For example, we obtain elegant DDH-based MACs with much shorter keys than the quadratic-sized key of the Naor-Reingold PRF. We also show that several natural (probabilistic) digital signature schemes, such as those by Boneh-Boyen and Waters, can be significantly optimized when “downgraded” into a MAC, both in terms of their efficiency (e.g., no bilinear pairings) and security assumptions (e.g., standard CDH instead of bilinear CDH). * For probabilistic MACs, unlike deterministic ones, unforgeability against a chosen message attack (uf-cma) alone does not imply security if the adversary can additionally make verification queries (uf-cmva). In fact, a number of elegant constructions, such as recently constructed MACs based on Learning Parity with Noise (LPN) and some of the new MACs constructed in this work, are uf-cma but not not uf-cmva secure by themselves. We give an efficient generic transformation from any uf-cma secure MAC which is "message-hiding" into a uf-cmva secure MAC. Applied to LPN-based MACs, this resolves the main open problem of Kiltz et al. from Eurocrypt '11. * While all our new MAC constructions immediately give efficient actively secure, two-round symmetric-key identification schemes, we also show a very simple, three-round actively secure identification protocol from any weak PRF. In particular, the resulting protocol is much more efficient than the trivial approach of building a regular PRF from a weak PRF.

Available format(s)
Secret-key cryptography
Publication info
Published elsewhere. EUROCRYPT 2012
MACidentification protocolsLPN
Contact author(s)
eike kiltz @ rub de
2012-10-29: last of 2 revisions
2012-02-10: received
See all versions
Short URL
Creative Commons Attribution


      author = {Yevgeniy Dodis and Eike Kiltz and Krzysztof Pietrzak and Daniel Wichs},
      title = {Message Authentication, Revisited},
      howpublished = {Cryptology ePrint Archive, Paper 2012/059},
      year = {2012},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.