3
$\begingroup$

Let $H_{1}(x)$, $H_{2}(x)$, ..., $H_{n}(x)$ be a list of $n$ secure one-way hash functions such that for a given input $x$ each $H_{i}(x) \neq H_{j}(x)$ when $i \neq j$. Give one hash function to each of $n$ people. No person should be able to reproduce the output of any other person's hash function.

For any inputs $x,y$ with $x \neq y$, is it possible to define a comparison function $F$ such that $F(H_{i}(x),H_{j}(x)) = true$ and $F(H_{i}(x),H_{j}(y)) = false$?

In other words if each person creates hash codes of the same inputs using different secure one-way hash functions, can I tell what hash codes were derived from the same input?

Improve this question
$\endgroup$
1
  • $\begingroup$ I'm pretty sure the answer would be "no" as this would require to actually compute the output for a given different user which is excluded by the first paragraph. I'm pretty sure, creating such a function would imply either inverting $H_i$ and / or actually computing $H_i$ which is also impossible. $\endgroup$
    – SEJPM
    Aug 22, 2015 at 20:58

1 Answer 1

Reset to default
4
$\begingroup$

Actually, if you define the $H_i$ functions properly, it can be done.

I'll make the simplifying assumption that we can treat the $H_i$ and $F$ functions as Oracles (that is, you're not allowed to look inside their implementation); I believe that it's still possible without that assumption (but the solution may be more complex).

For our primitives, we'll use FF1 with a secret key; and define:

$$H_i(x) = FF1_{key}( SHA256(x) || i )$$

This meets all the requirements of a secure hash function (e.g. it is collision resistant if we assume SHA256 is); in addition, the holder of $H_i$ cannot use it as a Oracle to compute $H_j$ for $i \ne j$ (as they don't know the $key$)

And, we can define a function $F$ that uses the secret key to decrypt both encrypted hashes, and compares the SHA256 values. This will correct tell if the two original messages where the same (unless we happen apon a collision in SHA256)

Improve this answer
$\endgroup$
4
  • $\begingroup$ Thanks Poncho, that is an innovative solution! But your curious comment about it still being possible without the Oracle assumption...could you offer any insight as to why you think it may be possible to lift that assumption? $\endgroup$
    – P. Anderson
    Aug 24, 2015 at 14:59
  • $\begingroup$ @P.Anderson: I was thinking about two different approaches; one just did the same approach, but using Whitebox cryptography. The other approach was to use public key crypto; one approach (extending the comparison function to include the $i, j$ values) would be to define an RSA modulus $m$ with secret factorization, and $H_i(x) = SHA256(x)^ i \bmod m$ (with obvious restrictions on the $i$ values), and defining $F(M_i, i, M_j, j) = (M_i^j == M_j^i) \bmod m$ $\endgroup$
    – poncho
    Aug 24, 2015 at 15:46
  • $\begingroup$ Thanks again Poncho, the second approach is what I was looking for! Would it make sense to choose the i values so that the greatest common divisor with the totient function is greater than 1 (will this prevent any chance of the SHA256 values from being discovered by there not being a RSA private key)? $\endgroup$
    – P. Anderson
    Aug 25, 2015 at 23:46
  • $\begingroup$ @P.Anderson: actually, after I wrote this, I realized that if $i$ and $j$ were relatively prime, you could reconstuct $SHA256(x)$ from $H_i(x)$ and $H_j(x)$. This isn't fatal, though; one way to make this work is to make our 'indicies' values which aren't relatively prime; for $H_i$, we use the exponent $3 \times 5 \times 7 \times ... \times p_n / p_i$, where $p_i$ is the ith odd prime (and where $n$ is the total number of indicies). That way, even with all the values $H_i$ other than $H_j$, we still can't recover $H_j$ $\endgroup$
    – poncho
    Aug 26, 2015 at 3:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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