Paper 2023/1083
Keyed Sum of Permutations: a simpler RP-based PRF
Abstract
Idealized constructions in cryptography prove the security of a primitive based on the security of another primitive. The challenge of building a pseudorandom function (PRF) from a random permutation (RP) has only been recently tackled by Chen, Lambooij and Mennink [CRYPTO 2019] who proposed Sum of Even-Mansour (SoEM) with a provable beyond-birthday-bound security. In this work, we revisit the challenge of building a PRF from an RP. On the one hand, we describe Keyed Sum of Permutations (KSoP) that achieves the same provable security as SoEM while being strictly simpler since it avoids a key addition but still requires two independent keys and permutations. On the other hand, we show that it is impossible to further simplify the scheme by deriving the two keys with a simple linear key schedule as it allows a non-trivial birthday-bound key recovery attack. The birthday-bound attack is mostly information-theoretic, but it can be optimized to run faster than a brute-force attack.
Metadata
- Available format(s)
-
PDF
- Category
- Secret-key cryptography
- Publication info
- Published elsewhere. CT-RSA 2023
- DOI
- 10.1007/978-3-031-30872-7_22
- Keywords
- RP-to-PRFSoEMKSoPbeyond-birthday-boundprovable security
- Contact author(s)
-
ferdinand sibleyras @ ntt com
yosuke todo @ ntt com - History
- 2023-07-16: approved
- 2023-07-12: received
- See all versions
- Short URL
- https://ia.cr/2023/1083
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2023/1083,
author = {Ferdinand Sibleyras and Yosuke Todo},
title = {Keyed Sum of Permutations: a simpler {RP}-based {PRF}},
howpublished = {Cryptology {ePrint} Archive, Paper 2023/1083},
year = {2023},
doi = {10.1007/978-3-031-30872-7_22},
url = {https://eprint.iacr.org/2023/1083}
}