**How to Build Pseudorandom Functions From Public Random Permutations**

*Yu Long Chen and Eran Lambooij and Bart Mennink*

**Abstract: **Pseudorandom functions are traditionally built upon block ciphers, but with the trend of permutation based cryptography, it is a natural question to investigate the design of pseudorandom functions from random permutations. We present a generic study of how to build beyond birthday bound secure pseudorandom functions from public random permutations. We first show that a pseudorandom function based on a single permutation call cannot be secure beyond the $2^{n/2}$ birthday bound, where n is the state size of the function. We next consider the Sum of Even-Mansour (SoEM) construction, that instantiates the sum of permutations with the Even-Mansour construction. We prove that SoEM achieves tight $2n/3$-bit security if it is constructed from two independent permutations and two randomly drawn keys. We also demonstrate a birthday bound attack if either the permutations or the keys are identical. Finally, we present the Sum of Key Alternating Ciphers (SoKAC) construction, a translation of Encrypted Davies-Meyer Dual to a public permutation based setting, and show that SoKAC achieves tight $2n/3$-bit security even when a single key is used.

**Category / Keywords: **secret-key cryptography / RP-to-PRF, SoEM, beyond the birthday bound

**Original Publication**** (with minor differences): **IACR-CRYPTO-2019

**Date: **received 23 May 2019, last revised 14 Dec 2021

**Contact author: **yulong chen at kuleuven be

**Available format(s): **PDF | BibTeX Citation

**Version: **20211214:215830 (All versions of this report)

**Short URL: **ia.cr/2019/554

[ Cryptology ePrint archive ]