## CryptoDB

### Paper: How to Build Pseudorandom Functions from Public Random Permutations

Authors: Yu Long Chen Eran Lambooij Bart Mennink DOI: 10.1007/978-3-030-26948-7_10 (login may be required) Search ePrint Search Google 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.
##### BibTeX
@article{crypto-2019-29863,
title={How to Build Pseudorandom Functions from Public Random Permutations},
booktitle={Advances in Cryptology – CRYPTO 2019},
series={Lecture Notes in Computer Science},
publisher={Springer},
volume={11692},
pages={266-293},
doi={10.1007/978-3-030-26948-7_10},
author={Yu Long Chen and Eran Lambooij and Bart Mennink},
year=2019
}