Farasha: A Provable Permutation-Based Parallelizable PRF

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.