International Association for Cryptologic Research

International Association
for Cryptologic Research


How to Build Pseudorandom Functions from Public Random Permutations

Yu Long Chen
Eran Lambooij
Bart Mennink
DOI: 10.1007/978-3-030-26948-7_10 (login may be required)
Search ePrint
Search Google
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.
Video from CRYPTO 2019
  title={How to Build Pseudorandom Functions from Public Random Permutations},
  booktitle={Advances in Cryptology – CRYPTO 2019},
  series={Lecture Notes in Computer Science},
  author={Yu Long Chen and Eran Lambooij and Bart Mennink},