# 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. Apr 17, 2016 at 9:59
• $g^x\bmod p$ with a $n$-bit prime sounds pretty standard and is really hard to invert. Apr 17, 2016 at 13:03
• Related question: crypto.stackexchange.com/questions/11576/… Apr 17, 2016 at 15:28
• @SEJPM That function is neither bijective nor does its output conform to $\{0,1\}^{n}$. Apr 17, 2016 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? Apr 17, 2016 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.