There is a function H : {0, 1}* → {0, 1}^n. On input a message m and two shares of it x, w such that m = x ⊕ w, the function outputs y = H(m) = H(x) ⊕ H(w). How would I find that this NOT a collision resistance hash function. That is, find two different messages m1, m2 such that they map to the same y.

  • 1
    $\begingroup$ HINT: Consider all input values of length $n+1$ and Hamming weight 1. From the hashes of these, you can construct the hashes of all inputs of length $n+1$. $\endgroup$
    – Daniel S
    Apr 12 at 1:19
  • $\begingroup$ That too long, just bit flip in $x$ and $w$ at the same postion. $\endgroup$
    – kelalaka
    Apr 12 at 17:09
  • $\begingroup$ @kelalaka. I tried that, but flipping bit x_i and w_i would not affect the ith bit output of x XOR w, meaning both messages would be equivalent. HOWEVER, this could change the hash value. $\endgroup$
    – sangaCat
    Apr 12 at 20:29


Your Answer

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