### Farasha: A Provable Permutation-based Parallelizable PRF

##### Abstract

The pseudorandom function Farfalle, proposed by Bertoni et al. at ToSC 2017, is a permutation based arbitrary length input and output PRF. At its core are the public permutations and feedback shift register based rolling functions. Being an elegant and parallelizable design, it is surprising that the security of Farfalle has been only investigated against generic cryptanalysis techniques such as differential/linear and algebraic attacks and nothing concrete about its provable security is known. To fill this gap, in this work, we propose Farasha, a new permutation-based parallelizable PRF with provable security. Farasha can be seen as a simple and provable Farfalle-like construction where the rolling functions in the compression and expansion phases of Farfalle are replaced by a uniform almost xor universal (AXU) and a simple counter, respectively. We then prove that in the random permutation model, the compression phase of Farasha can be shown to be an uniform AXU function and the expansion phase can be mapped to an Even-Mansour block cipher. Consequently, combining these two properties, we show that Farasha achieves a security of min(keysize, permutation size/2). Finally, we provide concrete instantiations of Farasha with AXU functions providing different performance trade-offs. We believe our work will bring new insights in further understanding the provable security of Farfalle-like constructions.

Available format(s)
Category
Secret-key cryptography
Publication info
Published elsewhere. SAC 2022
Keywords
Pseudo random function Farfalle Almost xor universal function
Contact author(s)
Ravindra Jejurikar @ tii ae
iRaghvendraRohit @ gmail com
History
2022-09-05: approved
See all versions
Short URL
https://ia.cr/2022/1150

CC BY

BibTeX

@misc{cryptoeprint:2022/1150,
author = {Najwa Aaraj and Emanuele Bellin and Ravindra Jejurikar and Marc Manzano and Raghvendra Rohit and Eugenio Salazar},
title = {Farasha: A Provable Permutation-based Parallelizable PRF},
howpublished = {Cryptology ePrint Archive, Paper 2022/1150},
year = {2022},
note = {\url{https://eprint.iacr.org/2022/1150}},
url = {https://eprint.iacr.org/2022/1150}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.