Paper 2023/1083

Keyed Sum of Permutations: a simpler RP-based PRF

Ferdinand Sibleyras, NTT Social Informatics Laboratories
Yosuke Todo, NTT Social Informatics Laboratories

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.

Available format(s)
Secret-key cryptography
Publication info
Published elsewhere. CT-RSA 2023
RP-to-PRFSoEMKSoPbeyond-birthday-boundprovable security
Contact author(s)
ferdinand sibleyras @ ntt com
yosuke todo @ ntt com
2023-07-16: approved
2023-07-12: received
See all versions
Short URL
Creative Commons Attribution


      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},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.