Beyond-birthday secure domain-preserving PRFs from a single permutation

This paper revisits the fundamental cryptographic problem of building pseudorandom functions (PRFs) from pseudorandom permutations (PRPs). We prove that, SUMPIP, i.e. \(P \oplus P^{-1}\), the sum of a PRP and its inverse, and EDMDSP, the single-permutation variant of the “dual” of the Encrypted Davies–Meyer scheme introduced by Mennink and Neves (CRYPTO 2017), are secure PRFs up to \(2^{2n/3}/n\) adversarial queries. To our best knowledge, SUMPIP is the first parallelizable, single-permutation-based, domain-preserving, beyond-birthday secure PRP-to-PRF conversion method.