Efficient Parallelizable Hashing Using Small Non-Compressing Primitives

© 2015, Springer-Verlag Berlin Heidelberg. A well-established method of constructing hash functions is to base them on non-compressing primitives, such as one-way functions or permutations. In this work, we present S r , an rn-to-n-bit compression function (for r≥ 1) making 2 r- 1 calls to n-to-n-bit primitives (random functions or permutations). S r compresses its inputs at a rate (the amount of message blocks per primitive call) up to almost 1/2, and it outperforms all existing schemes with respect to rate and/or the size of underlying primitives. For instance, instantiated with the 1600 -bit permutation of NIST’s SHA-3 hash function standard, it offers about 800 -bit security at a rate of almost 1/2, while SHA-3-512 itself achieves only 512 -bit security at a rate of about 1/3. We prove that S r achieves asymptotically optimal collision security against semi-adaptive adversaries up to almost 2 n/2 queries and that it can be made preimage secure up to 2 n queries using a simple tweak.status: publishe