### On the Adaptive Security of MACs and PRFs

Andrew Morgan, 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.

Available format(s)
Category
Foundations
Publication info
A major revision of an IACR publication in ASIACRYPT 2020
Keywords
impossibilitysecurity lossmulti-user securitypseudorandom functionsmessage authentication codesmeta-reduction
Contact author(s)
asmorgan @ cs cornell edu
History
Short URL
https://ia.cr/2020/1090

CC BY

BibTeX

@misc{cryptoeprint:2020/1090,
author = {Andrew Morgan and Rafael Pass and Elaine Shi},
title = {On the Adaptive Security of MACs and PRFs},
howpublished = {Cryptology ePrint Archive, Paper 2020/1090},
year = {2020},
note = {\url{https://eprint.iacr.org/2020/1090}},
url = {https://eprint.iacr.org/2020/1090}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.