Paper 2020/1090
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.
Metadata
- Available format(s)
-
PDF
- 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
- 2020-09-15: received
- Short URL
- https://ia.cr/2020/1090
- License
-
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},
url = {https://eprint.iacr.org/2020/1090}
}
