# Permutation of keys that guarantees different hashes

Suppose I have two values to be hashed, $x$ and $y$. Is there a hash function $H$ with the following properties?

$H(x) = H(y), \; H(m(x)) \neq H(m(y))$

Where $m$ is a permutation function that may depend on $H$.

Edit: The corrected question is, if $H(x) = H(y)$, them is it possible to make any permutation $m$ so that $H(m(x)) \neq H(m(y))$?

• So if $x==y$, then $H(x)\neq H(y)$? – mikeazo Jan 7 '16 at 15:48
• You might want to clarify your question. The only functions that satisfy $H(x) = H(y)\ \forall x \ne y$ are constant ones, and those obviously cannot satisfy the second criterion. So, as written, the answer is trivially "no." – Ilmari Karonen Jan 7 '16 at 16:02
• @IlmariKaronen not necessarily. Hash functions may collide, so for different values $x$ and $y$, a hash $H$ may yield the same value. The point, if this happens, and only if this happens, can I make any kind of change $m$ to $x$ and $y$ that will guarantee a different result of $H$? – petermlm Jan 7 '16 at 16:51
• @fgrieu, yes that is it – petermlm Jan 7 '16 at 17:18
• @fgrieu: I suspect the OP actually wants $$\exists H,m\ \forall x,y: (x \ne y \land H(x) = H(y)) \implies H(m(x)) \ne H(m(y)),$$ rather than $$\exists H,x,y\ \forall m: x \ne y \land H(x) = H(y) \land (m \ne {\rm id} \implies H(m(x)) \ne H(m(y))).$$ – Ilmari Karonen Jan 7 '16 at 17:50

I assume you're asking whether there exists a hash function $H: \{0,1\}^* \to \{0,1\}^\ell$, and a permutation $m: \{0,1\}^* \to \{0,1\}^*$, such that $$H(x) = H(y) \implies H(m(x)) \ne H(m(y))$$ for all $x \ne y$.
The answer, alas, is no — there is no such $H$ and $m$.
If there was, we could construct a collision-free hash function $H': \{0,1\}^* \to \{0,1\}^{2\ell}$ as $$H'(x) = H(x) \| H(m(x)).$$ But since the set $\{0,1\}^*$ is infinite, while $\{0,1\}^{2\ell}$ is finite, this is clearly impossible.
More generally, the same argument shows that no such $H$ and $m$ can exist if the input domain of $H$ has more than $n^2$ elements, where $n = 2^\ell$ is the number of possible outputs of $H$.