Search

This paper revisits the fundamental cryptographic problem of building pseudorandom functions (PRFs) from pseudorandom permutations (PRPs). We prove that, 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 (CRYPTO 2017), are secure PRFs up to 2 2 n / 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. [ABSTRACT FROM AUTHOR]

The idea of double block length hashing is to construct a compression function on 2 n bits using a block cipher with an n-bit block size. All optimally secure double block length hash functions known in the literature employ a cipher with a key space of double block size, 2 n-bit. On the other hand, no optimally secure compression functions built from a cipher with an n-bit key space are known. Our work deals with this problem. Firstly, we prove that for a wide class of compression functions with two calls to its underlying n-bit keyed block cipher collisions can be found in about $$2^{n/2}$$ queries. This attack applies, among others, to functions where the output is derived from the block cipher outputs in a linear way. This observation demonstrates that all security results of designs using a cipher with 2 n-bit key space crucially rely on the presence of these extra n key bits. The main contribution of this work is a proof that this issue can be resolved by allowing the compression function to make one extra call to the cipher. We propose a family of compression functions making three block cipher calls that asymptotically achieves optimal collision resistance up to $$2^{n(1-\varepsilon )}$$ queries and preimage resistance up to $$2^{3n(1-\varepsilon )/2}$$ queries, for any $$\varepsilon >0$$ . To our knowledge, this is the first optimally collision secure double block length construction using a block cipher with single length key space. We additionally prove this class of functions indifferentiable from random functions in about $$2^{n/2}$$ queries, and demonstrate that no other function in this direction achieves a bound of similar kind. [ABSTRACT FROM AUTHOR]