Cryptology ePrint Archive: Report 2019/554

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:

[ Cryptology ePrint archive ]