Cryptology ePrint Archive: Report 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.

Category / Keywords: secret-key cryptography / authentication, provable security, permutation, beyond-birthday security, pseudorandom function, universal hashing

Original Publication (with major differences): ACNS 2019

Date: received 24 Apr 2019

Contact author: moch at uni-mannheim de,eik list@uni-weimar de

Available format(s): PDF | BibTeX Citation

Version: 20190427:184031 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]