Message Authentication, Revisited

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 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 Kiltz et al. from Eurocrypt’11; By using our transformation on their constructions, we get the first efficient MACs from the LPN assumption.

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.