# A bijective hash function

Suppose:

• $H: \{0,1\}^{n} \rightarrow \{0,1\}^{n}$.
• $H$ is bijective.
• It is difficult to derive $x$ from $H(x)$.

Is this type of function possible? What would the strength of it be?

I realize that RSA and discrete logarithms can fulfill this, but I was thinking of using standard operators instead of those two. Other primitives could be acceptable.

• Where is the interest of this construction? Consider that a random permutation can solve this. – Robert NACIRI Apr 17 '16 at 9:59
• $g^x\bmod p$ with a $n$-bit prime sounds pretty standard and is really hard to invert. – SEJPM Apr 17 '16 at 13:03
• Related question: crypto.stackexchange.com/questions/11576/… – Samuel Neves Apr 17 '16 at 15:28
• @SEJPM That function is neither bijective nor does its output conform to $\{0,1\}^{n}$. – Melab Apr 17 '16 at 15:29
• @RobertNAICRI I am unable to remember the first reason. The second reason is the output function of Skein which is used, I think, to prevent a length extension attack. How can a random permutation solve this when they are purely imaginary? – Melab Apr 17 '16 at 17:57

On the practical side of things, if your hypothetical function is hard to invert, and assuming collisions are hard to find, why does it matter that it be bijective? For sufficiently large $n$ you can't construct a counterexample anyway, so a hash function may as well be bijective as far as anyone cares.