# Is there an efficient algorithm that allows to construct a cryptographically secure $n$-bit hash function based on two unkeyed $n$-bit permutations?

Let $$f(x)$$ and $$g(x)$$ denote two independent, “ideal”, unkeyed, public $$n$$-bit permutations (two publicly known bijective functions that produce $$n$$-bit outputs from $$n$$-bit inputs), where $$n$$ is an arbitrary natural number greater than or equal to $$3$$ (the number $$3$$ is here because it is the minimal size of a “cryptographically significant” S-Box).

Does there exist an efficient iterative algorithm (based on $$f(x)$$ and $$g(x)$$ as the underlying functions) that allows to construct a cryptographically secure $$n$$-bit hash function for $$k$$-bit inputs, assuming that $$k$$ is an arbitrary natural number greater than or equal to zero (that is, there should be no limit on the maximum length of the input)?

• Intermix $f$ and $g$ using Feistel network? – DannyNiu Feb 24 at 5:36
• Why can't you "just" use a Sponge construction with $f$? – SEJPM Feb 24 at 9:21
• @SEJPM: if I use a sponge construction with the single underlying $n$-bit permutation, the size of the cryptographically secure hash output will be significantly less than $n$. For example, SHA-3 uses the $1600$-bit underlying permutation, but the size of hash is $512$ bits. – lyrically wicked Feb 24 at 9:41
• @lirycally-wicked that is wrong. With a sponge you can have unbounded output, as in SHAKE. You just need to restrict the input size to n-c where c is the double of the security you target. – Ruggero Feb 24 at 10:08
• @lirycally-wicked No. The squeezing phase, where you produce the output, can require multiple permutation calls and for each one it outputs the size of the rate. If your rate is 1, you can have hashes of 256 bits just by doing 256 permutations in the squeezing phase. – Ruggero Feb 26 at 9:17

It is impossible to construct a collision-resistant hash function from one-way permutations, via a black-box construction. Thus, the answer in principle is no; such a construction is impossible. Finding collisions on a one-way street: Can secure hash functions be based on general assumptions? by Simon (Eurocrypt'98). This answer does not relate to heuristic constructions, but you cannot do this with a proof of security (unless it's not black box).

The question here actually relates to "ideal" permutations, and under such an assumption it may be different. (Although, I'm not sure what is meant by "public" ideal.) My answer referred to (non-ideal) one-way permutations.

• How do sponge-based hashes fit into this picture? – SEJPM Feb 26 at 10:24
• You need an ideal assumption. I just noticed that this was actually in the question, so my answer is wrong. I will update. – Yehuda Lindell Feb 26 at 11:27
• And even the security of the XOR of two permutations cannot help to construct the desired hash function? – lyrically wicked Feb 27 at 5:22
• The XOR of two pseudorandom permutations is a pseudorandom function (and that's what the link shows). It says nothing about collision resistance. – Yehuda Lindell Feb 27 at 6:45

If I understand the question correctly, one such possible construction would be something that was used in the SHA-3 competition candidate Grøstl, where an iterated compression function is built from two fixed permutations $$P$$ and $$Q$$: The security proof of that construction is based on the paper: P.-A. Fouque, J. Stern, and S. Zimmer. Cryptanalysis of Tweaked Versions of SMASH and Reparation. Selected Areas in Cryptography 2008, LNCS 5381, Springer, 2009

• The size of $P$ and $Q$ in this construction is equal to $2n$ (where $n$ is the size of hash). My question implies that the size of each of the two permutations is equal to $n$. – lyrically wicked Feb 28 at 4:17