Back to Search
Start Over
Analysis of the single-permutation encrypted Davies-Meyer construction.
- Source :
- Designs, Codes & Cryptography; Dec2018, Vol. 86 Issue 12, p2703-2723, 21p
- Publication Year :
- 2018
-
Abstract
- 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]
Details
- Language :
- English
- ISSN :
- 09251022
- Volume :
- 86
- Issue :
- 12
- Database :
- Complementary Index
- Journal :
- Designs, Codes & Cryptography
- Publication Type :
- Academic Journal
- Accession number :
- 132480835
- Full Text :
- https://doi.org/10.1007/s10623-018-0470-9