Efficient parallelizable hashing using small non-compressing primitives

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 (rge 1)) making (2r-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.