Paper 2022/1172

On the security of keyed hashing based on an unkeyed block function

Jonathan Fuchs, Radboud University Nijmegen
Yann Rotella, Université Paris-Saclay
Joan Daemen, Radboud University Nijmegen

In this paper we study the security of two constructions for variable-length universal hash functions by means of their universality. Both constructions make use of a fixed-length unkeyed function that we call a block function. One construction is serial and is an idealization of the compression phase of Pelican-MAC. The other construction is parallel and is an idealization of the compression phase of Farfalle. Both are instances of a class of functions we call semi-group accumulators. We prove that the universality of these constructions is fully determined by the differential probability of block function differentials and, if not a permutation, the relative frequency of block function outputs. We show that both block function parallelization and serialization have equal security (against forgery) in the Wegman-Carter(-Shoup) construction. However, for the block functions we target, parallelization can provide significantly better security than serialization in the Protected Hash (PH) construction. Moreover, below a certain data limit, PH provides better security than WC(S) for the block function parallelization, despite the fact that it does not require a nonce. We show evidence of this effect by taking Xoodoo[3] as the block function .

Available format(s)
Secret-key cryptography
Publication info
Keyed hashing Universality Differential probability Parallel Serial Permutation
Contact author(s)
jonathan fuchs @ ru nl
yann rotella @ uvsq fr
joan daemen @ ru nl
2022-09-09: approved
2022-09-07: received
See all versions
Short URL
Creative Commons Attribution


      author = {Jonathan Fuchs and Yann Rotella and Joan Daemen},
      title = {On the security of keyed hashing based on an unkeyed block function},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1172},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.