Collision resistant hash functions 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?
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.