4
$\begingroup$

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))$?

$\endgroup$
8
  • $\begingroup$ So if $x==y$, then $H(x)\neq H(y)$? $\endgroup$ – mikeazo Jan 7 '16 at 15:48
  • 3
    $\begingroup$ 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." $\endgroup$ – Ilmari Karonen Jan 7 '16 at 16:02
  • $\begingroup$ @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$? $\endgroup$ – petermlm Jan 7 '16 at 16:51
  • 2
    $\begingroup$ @fgrieu, yes that is it $\endgroup$ – petermlm Jan 7 '16 at 17:18
  • 3
    $\begingroup$ @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))).$$ $\endgroup$ – Ilmari Karonen Jan 7 '16 at 17:50
6
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.