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).Weprovethat,SUMPIP,i.e. P⊕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(CRYPTO2017), are secure PRFs up to 22n/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