My scenario is as follows:

Two entities $A_1$, $A_2$ host same versions of replicated data $M$. An entity $A_1$ computes $h_1 = H_1(M)$ and another entity $A_2$ computes $h_2 = H_2(M)$.

Is there any set of functions $H$, $H_1$ and $H_2$ so that Alice, after receiving $h_1$ and $h_2$ can check $H(h_1) = h_2$, but $A_2$ cannot compute $h_2$ using $h_1$?

More precisely, there be two ways to compute $H_2$ with two different keys, a direct way and 2-step way. $A_2$ computes $h_2$ through direct way and Alice compute it through $h_2 = H(H_1(M))$.

  • $\begingroup$ Please check if my edits didn't change the question in any meaningful way. $\endgroup$
    – Maarten Bodewes
    May 23, 2018 at 14:47
  • 1
    $\begingroup$ What's wrong with Alice drawing a key pair for a deterministic asymmetric encryption scheme $E/D$ (RSA..); $H_2$ a public hash (SHA-512), $H_1=E\circ H_2$, $H=D$ ? If $H$ and $H_2$ have a key, they are not hash functions; they are I guess keyed PRF like HMAC. Is that correct? Is $H_1$ supposed/allowed to be keyed too? $\endgroup$
    – fgrieu
    May 23, 2018 at 15:36
  • $\begingroup$ That way A1 is able to compute H1 using H2's output. I'm seeking a way to avoid collusion of A1 and A2, that is, they can not use the output of each other. They should be able to compute the desired output only if they possess file M $\endgroup$
    – Reyhan
    May 23, 2018 at 21:06
  • $\begingroup$ Two questions: 1) is the requirement symmetric; is it also necessary that it is difficult to compute $h_1$ using $h_2$? 2) is it necessary for Alice to reconstruct $h_2$ from $h_1$? Would it be sufficient if there was an efficient way to check if an $h_1$ and $h_2$ were hashes of the same $M$? $\endgroup$
    – poncho
    May 24, 2018 at 3:10
  • $\begingroup$ As I said, I'm seeking a way to avoid collusion of A1 and A2, If their outputs be the same, they can simply collude $\endgroup$
    – Reyhan
    May 24, 2018 at 8:20


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.

Browse other questions tagged or ask your own question.