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
Abstract

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, while the sponge/duplex can squeeze at most $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. This construction could be seen as a generalization of the construction underlying the stream cipher family Salsa. Furthermore, we define a simple mode on top of Kirby that turns it into a deck function with parallel expansion. This is similar to Farfalle but it has a much smaller memory footprint. Furthermore we prove that in the Kirby construction, the leakage of intermediate states does not allow recovering the key or earlier states.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Preprint.
Keywords
permutation-based cryptographyprovable securitymulti-user securityPRFlightweightleakage resilience
Contact author(s)
charlotte lefevre @ ru nl
yanis belkheyar @ ru nl
joan daemen @ ru nl
History
2024-04-09: revised
2023-10-05: received
See all versions
Short URL
https://ia.cr/2023/1520
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2023/1520,
      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},
      url = {https://eprint.iacr.org/2023/1520}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.