Dodis, Yevgeniy; Kiltz, Eike; Pietrzak, Krzysztof; Wichs, Daniel Message authentication, revisited. (English) Zbl 1297.94117 Pointcheval, David (ed.) et al., Advances in cryptology – EUROCRYPT 2012. 31st annual international conference on the theory and applications of cryptographic techniques, Cambridge, UK, April 15–19, 2012. Proceedings. Berlin: Springer (ISBN 978-3-642-29010-7/pbk). Lecture Notes in Computer Science 7237, 355-374 (2012). Summary: 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: \(\bullet\) 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. \(\bullet\) 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 ). We give an efficient generic transformation from any uf-cma secure MAC which is “message-hiding” into a uf-cmva secure MAC. This resolves the main open problem of E. Kiltz et al. [Advances in cryptology – EUROCRYPT 2011, Lect. Notes Comput. Sci. 6632, 7–26 (2011; Zbl 1281.94083)]. By using our transformation on their constructions, we get the first efficient MACs from the LPN assumption. \(\bullet\) 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.For the entire collection see [Zbl 1239.94002]. Cited in 3 ReviewsCited in 11 Documents MSC: 94A62 Authentication, digital signatures and secret sharing Citations:Zbl 1281.94083 PDF BibTeX XML Cite \textit{Y. Dodis} et al., Lect. Notes Comput. Sci. 7237, 355--374 (2012; Zbl 1297.94117) Full Text: DOI OpenURL