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
Creative Commons Attribution
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},
      note = {\url{https://eprint.iacr.org/2019/422}},
      url = {https://eprint.iacr.org/2019/422}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.