Paper 2022/1172

On the Security of Keyed Hashing Based on Public Permutations

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

Doubly-extendable cryptographic keyed functions (deck) generalize the concept of message authentication codes (MAC) and stream ciphers in that they support variable-length strings as input and return variable-length strings as output. A prominent example of building deck functions is Farfalle, which consists of a set of public permutations and rolling functions that are used in its compression and expansion layers. By generalizing the compression layer of Farfalle, we prove its universality in terms of the probability of differentials over the public permutation used in it. As the compression layer of Farfalle is inherently parallel, we compare it to a generalization of a serial compression function inspired by Pelican-MAC. The same public permutation may result in different universalities depending on whether the compression is done in parallel or serial. The parallel construction consistently performs better than the serial one, sometimes by a big factor. We demonstrate this effect using Xoodoo[3], which is a round-reduced variant of the public permutation used in the deck function Xoofff.

Available format(s)
Secret-key cryptography
Publication info
Keyed hashingUniversalityDifferential probabilityParallelSerialPermutation
Contact author(s)
jonathan fuchs @ ru nl
yann rotella @ uvsq fr
joan daemen @ ru nl
2023-06-06: last of 3 revisions
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 Public Permutations},
      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.