Paper 2019/422
Parallelizable MACs Based on the Sum of PRPs with Security Beyond the Birthday Bound
Alexander Moch and Eik List
Abstract
The combination of universal hashing and encryption is a fundamental paradigm for the construction of symmetric-key MACs, dating back to the seminal works by Wegman and Carter, Shoup, and Bernstein. While fully sufficient for many practical applications, the Wegman-Carter construction, however, is well-known to break if nonces are ever repeated, and provides only birthday-bound security if instantiated with a permutation. Those limitations inspired the community to several recent proposals that addressed them, initiated by Cogliati et al.'s Encrypted Wegman-Carter Davies-Meyer (EWCDM) construction. This work extends this line of research by studying two constructions based on the sum of PRPs: (1) a stateless deterministic scheme that uses two hash functions, and (2) a nonce-based scheme with one hash-function call and a nonce. We show up to 2n/3-bit security for both of them if the hash function is universal. Compared to the EWCDM construction, our proposals avoid the fact that a single reuse of a nonce can lead to a break.
Metadata
- Available format(s)
-
PDF
- Category
- Secret-key cryptography
- Publication info
- Published elsewhere. Major revision. ACNS 2019
- Keywords
- authenticationprovable securitypermutationbeyond-birthday securitypseudorandom functionuniversal hashing
- Contact author(s)
-
moch @ uni-mannheim de
eik list @ uni-weimar de - History
- 2019-07-01: revised
- 2019-04-27: received
- See all versions
- Short URL
- https://ia.cr/2019/422
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2019/422,
author = {Alexander Moch and Eik List},
title = {Parallelizable {MACs} Based on the Sum of {PRPs} with Security Beyond the Birthday Bound},
howpublished = {Cryptology {ePrint} Archive, Paper 2019/422},
year = {2019},
url = {https://eprint.iacr.org/2019/422}
}
