Cryptology ePrint Archive: Report 2020/1090

On the Adaptive Security of MACs and PRFs

Andrew Morgan and Rafael Pass and Elaine Shi

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.

Category / Keywords: foundations / impossibility, security loss, multi-user security, pseudorandom functions, message authentication codes, meta-reduction

Original Publication (with major differences): IACR-ASIACRYPT-2020

Date: received 10 Sep 2020

Contact author: asmorgan at cs cornell edu

Available format(s): PDF | BibTeX Citation

Version: 20200915:111512 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]