1
$\begingroup$

Given a collision-resistant hash function $H(x)$, say SHA256, and I devise another hash function by $H'(x)=\sum^{m}_{1}H(x||i) \mod p$. The summation is defined on finite field of prime order $p$.

Is the new hash function $H'(x)$ still collision resistant? How hard is it to find a collision? Any advice would be greatly appreciated!

$\endgroup$
  • 2
    $\begingroup$ I don't think there's anything that can be said without stronger assumptions on $H$ than just collision resistance. In particular, even for $m=2$, it's easy to construct artificial $H$ (by tweaking an existing collision-resistant hash for a few inputs) that are collision resistant, but for which $H'$ has trivial collisions. $\endgroup$ – Ilmari Karonen Jul 23 '19 at 5:57
  • 2
    $\begingroup$ @IlmariKaronen: I believe that's the answer: "$H'$ is not necessarily collision resistant because (assuming there exists a collision resistant hash function) we can devise an $H$ which is collision resistant, but $H'$ is not". Trivial example: assuming $H^*$ is a collision resistant hash function, define $H(x) = p \times H^*(x)$... $\endgroup$ – poncho Jul 23 '19 at 11:54
  • $\begingroup$ Or, are you asking "if we assume a random (or not deliberately malformed) $H$, how difficult would this be?" $\endgroup$ – poncho Jul 23 '19 at 22:18
  • $\begingroup$ @poncho, sorry for this very late reply. In my case, we could just assume $H$ to be sha256. Then how hard the $H'$ can be? $\endgroup$ – aphasiayc Sep 2 '19 at 13:21
2
$\begingroup$

Counterexample [from poncho in comments]: let $H_0\colon \{0,1\}^* \to \{0,1\}^{256}$; then $H(x) := p \cdot H_0(x)$, where $H_0(x)$ is interpreted as an integer in little-endian, is obviously collision-resistant but $H'(x) := \sum H(\cdots) \bmod p$ is identically zero and therefore very much not collision-resistant no matter what goes in the ellipsis.

| improve this answer | |
$\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.