Paper 2019/554

How to Build Pseudorandom Functions From Public Random Permutations

Yu Long Chen, Eran Lambooij, and Bart Mennink


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.

Available format(s)
Secret-key cryptography
Publication info
A minor revision of an IACR publication in CRYPTO 2019
RP-to-PRFSoEMbeyond the birthday bound
Contact author(s)
yulong chen @ kuleuven be
2021-12-14: last of 3 revisions
2019-05-24: received
See all versions
Short URL
Creative Commons Attribution


      author = {Yu Long Chen and Eran Lambooij and Bart Mennink},
      title = {How to Build Pseudorandom Functions From Public Random Permutations},
      howpublished = {Cryptology ePrint Archive, Paper 2019/554},
      year = {2019},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.