CryptoDB
How to Build Pseudorandom Functions from Public Random Permutations
| Authors: | |
|---|---|
| Download: |
|
| 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
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
}