Question

Topic: Intro to Cryptography

Collision-resistant hash function Let (Gen1, H1) and (Gen2, H2) be two hash functions, where at least one of them is collision resistant. Define (Gen, H) in the following. Prove or disprove that (Gen, H) is necessarily collision resistant. (a) Gen runs Gen, and Gen, to obtain keys 81 and 82, respectively. Then define H$1,82 (2) := H (2)| HP (). (b) Gen runs Gen, and Gen, to obtain keys and s2, respectively. Then define H81,82 () := HH ()

Answer 1

Note: please upvote my answer so that i can solve all your doubts and problems.

Collision resistance is a property of cryptography hash functions:

a hash function is collision resistant only if it is hard to find two inputs from that hash to the same output;

that is, two inputs a and b such that H(a) = H(b).

Every hash function with more inputs as compared to outputs will necessarily have collisions.

Ans.(a)

H_a is collision-resistant: As H_a(x) = H_a(y) as it implies that H₁(x) = H₁(y) and H₂(x) = H₂(y) any adversary which helps to find a collision for H_a can be used to construct an adversary which finds the collision for both H₁ or H₂.

Ans.(b)

H_b is not collision-resistant: Assuming H₁ is the constant zero function (for all keys), it follows that H_b(x) = 0||H₂(0) for any x.