Analysis of the single-permutation encrypted Davies-Meyer construction.

We consider the so-called Encrypted Davies-Meyer (EDM) construction, which turns a permutation P on {0,1}n into a function from {0,1}n to {0,1}n defined as P(P(x)⊕x). A similar construction using two independent permutations, namely P′(P(x)⊕x), was previously analyzed by Cogliati and Seurin (Advances in cryptology—CRYPTO 2016 (Proceedings, Part I). LNCS, vol 9814, pp. 121-149, 2016) who showed that when P and P′ are secret and random, then any black-box adversary needs at least roughly 22n/3 queries to distinguish the construction from a uniformly random function from {0,1}n to {0,1}n. In this paper, we focus on the single-permutation variant of the construction. Our main result is that the PRF-security of the single-permutation EDM construction is also (at least) roughly 22n/3, in the sense that any black-box adversary needs at least this number of queries to distinguish the construction from a uniformly random function. This yields the first PRP-to-PRF conversion method which uses a single permutation, does not shrink the original domain nor range of the permutation, and provides security beyond the birthday bound. [ABSTRACT FROM AUTHOR]