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

Yu Long Chen, 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.

Available format(s)
Category
Secret-key cryptography
Publication info
A minor revision of an IACR publication in CRYPTO 2019
Keywords
RP-to-PRFSoEMbeyond the birthday bound
Contact author(s)
yulong chen @ kuleuven be
History
2021-12-14: last of 3 revisions
See all versions
Short URL
https://ia.cr/2019/554

CC BY

BibTeX

@misc{cryptoeprint:2019/554,
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{https://eprint.iacr.org/2019/554}},
url = {https://eprint.iacr.org/2019/554}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.