Welcome to the resource topic for 2023/1083
Title:
Keyed Sum of Permutations: a simpler RP-based PRF
Authors: Ferdinand Sibleyras, Yosuke Todo
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.
ePrint: https://eprint.iacr.org/2023/1083
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .