The idea of double block length hashing is to construct a compression function on 2n bits using a block cipher with an n-bit block size. All optimally secure double length hash functions known in the literature employ a cipher with a key space of double block size, 2n-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 2n-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−ε) queries and preimage resistance up to 2 3n(1−ε)/2 queries, for any ε > 0. To our knowledge, this is the first optimally collision secure double block length construction using a block cipher with single length key space. 1 In the iteration collision resistance is proven up to 2 3n/5 queries for MDC-2 [27] and 2 2n/3 queries for MJH [10] .
In REF , Mennink presented a class of compression functions making three block cipher calls with optimal 2 n collision security and preimage security up to 2 3n/2 queries.
Optimal collision security in double block length hashing with single length key
ASIACRYPT
Computer Science