Paper 2022/1150

Farasha: A Provable Permutation-based Parallelizable PRF

Najwa Aaraj, Technology Innovation Institute, Abu Dhabi, UAE
Emanuele Bellin, Technology Innovation Institute, Abu Dhabi, UAE
Ravindra Jejurikar, Technology Innovation Institute, Abu Dhabi, UAE
Marc Manzano, SandboxAQ, Palo Alto, CA, United States
Raghvendra Rohit, Technology Innovation Institute, Abu Dhabi, UAE
Eugenio Salazar, Technology Innovation Institute, Abu Dhabi, UAE

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)
Secret-key cryptography
Publication info
Published elsewhere. SAC 2022
Pseudo random function Farfalle Almost xor universal function
Contact author(s)
Ravindra Jejurikar @ tii ae
iRaghvendraRohit @ gmail com
2022-09-05: approved
2022-09-05: received
See all versions
Short URL
Creative Commons Attribution


      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{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.