Paper 2023/1520

Kirby: A Robust Permutation-Based PRF Construction

Charlotte Lefevre, Radboud University Nijmegen, CSEM
Yanis Belkheyar, Radboud University Nijmegen
Joan Daemen, Radboud University Nijmegen

We present a construction, called Kirby, for building a variable-input-length pseudorandom function (VIL-PRF) from a $b$-bit permutation. For this construction we prove a tight bound of $b/2$ bits of security on the PRF distinguishing advantage in the random permutation model and in the multi-user setting. Similar to full-state keyed sponge/duplex, it supports full-state absorbing and additionally supports full-state squeezing, where the latter can at most squeeze $b-c$ bits per permutation call for a security level of $c$ bits. This advantage is especially relevant on constrained platforms when using a permutation with small width $b$. For instance, for $b=256$ at equal security strength the squeezing rate of Kirby is twice that of keyed sponge/duplex. We define a simple mode on top of Kirby that turns it into a deck function with parallel expansion. This deck function is suited for lightweight applications in the sense that it has a low memory footprint. Moreover, for short inputs it can be used for low-latency stream encryption: the time between the availability of the input and the keystream is only a single permutation call. Another feature that sets Kirby apart from other constructions is that leakage of an intermediate state does not allow recovering the key or $\textit{earlier states}$.

Available format(s)
Secret-key cryptography
Publication info
permutation-based cryptographyprovable securitymulti-user securityPRFlightweightdeck function
Contact author(s)
charlotte lefevre @ ru nl
yanis belkheyar @ ru nl
joan daemen @ ru nl
2023-10-06: approved
2023-10-05: received
See all versions
Short URL
Creative Commons Attribution


      author = {Charlotte Lefevre and Yanis Belkheyar and Joan Daemen},
      title = {Kirby: A Robust Permutation-Based PRF Construction},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1520},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.