Message Authentication, Revisited.
Yevgeniy Dodis, Eike Kiltz, Krzysztof Pietrzak, Daniel Wichs · 2012
Traditionally, symmetric-keymessage 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 showseveralnew probabilisticMAC constructionsfromavarietyofgeneralassumptions, 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