Let (Gen1,H1) and (Gen2,H2) be two hash functions. Define (Gen,H) so that Gen runs Gen1 and Gen2 to obtain keys s1 and s2, respectively. Then define Hs1,s2(x)=Hs1(x)||Hs2(x).

a) Prove that if at least one of (Gen1,H1) and (Gen2,H2) aris collision resisistant, then (Gen,H) is collision resistant.

b) Determine whether an analogous claim holds for second pre-image resistance and pre-image resistance, respectively. Prove your answer in each case.

Now assume H is any collision reistant hash function. Then is the composition H o H necessarily collision resistant?

  • 1
    $\begingroup$ This isn't a question answering service. What have you tried? Where are you stuck? $\endgroup$
    – mikeazo
    Nov 17, 2014 at 14:21
  • $\begingroup$ Does the proof-of-work tag even related here? $\endgroup$
    – Bush
    Nov 17, 2014 at 23:26

1 Answer 1


Since it's your homework, I'll only hive you the direction and not a full formal proof:

a) if at least one of H1 and H2 are collision resistant then H is too. Because if H is not coll-resistant then it's possible to find x and x' s.t. H(x)=H(x') so H(x)=H1(x)||H2(x)=H1(x')||H2(x')=H(x') which means that H1(x)=H1(x') and H2(x)=H2(x') so we found a collision in both H1 and H2.

b) About preimage res, if H is not preimage-res then given y it is possible to find x such that H(x)=y. We know that y=y1||y2=H1(x)||H2(x), thus you can find the preimage of y in both H1 and H2 as before.

c) about the composition, it is clear that a composition is also coll-res. Assume that H(H(•)) is not coll-res then it immediately means that H(•) is not coll-rea, by contradiction to the fact that H is coll-res.


Your Answer

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

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