International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: On the Adaptive Security of MACs and PRFs

Andrew Morgan
Rafael Pass
Elaine Shi
DOI: 10.1007/978-3-030-64837-4_24
Search ePrint
Search Google
Abstract: We consider the security of two of the most commonly used cryptographic primitives--message authentication codes (MACs) and pseudorandom functions (PRFs)--in a multi-user setting with adaptive corruption. Whereas is it well known that any secure MAC or PRF is also multi-user secure under adaptive corruption, the trivial reduction induces a security loss that is linear in the number of users. Our main result shows that black-box reductions from "standard" assumptions cannot be used to provide a tight, or even a linear-preserving, security reduction for adaptive multi-user secure deterministic stateless MACs and thus also PRFs. In other words, a security loss that grows with the number of users is necessary for any such black-box reduction.
Video from ASIACRYPT 2020
  title={On the Adaptive Security of MACs and PRFs},
  booktitle={Advances in Cryptology - ASIACRYPT 2020},
  author={Andrew Morgan and Rafael Pass and Elaine Shi},