3 ms·

Collision resistance implies onewayness for compressing hash functions. You can invert a hashed value, and if your inversion procedure is randomised, then there

• chias 10y ago
  > Collision resistance implies onewayness for compressing hash functions. No it doesn't. These are independent properties. That is, collision resistance does not imply onewayness, and onewayness does not imply collision resistance. Collision Resistance: it is hard to find x != x' such that h(x) = h(x') One Wayness: Given y, an n-bit string randomly chosen from the output space of h(), it is hard to find any x such that h(x) = y. Proof that CR does not imply OW: Suppose g() is collision resistant and outputs n bits. Define h(x) to be 0x if x is n bits long, otherwise 1x. Collisions are hard to find: if y starts with 1 there are no collisions, and if it starts with 0 then you'd need to find a collision in g(), which is collision resistant. h() is not one way: given a random y in the output space, with probability 1/2 it is trivial to find an x such that h(x) = y. Proof that OW does not imply CR: Suppose that g() is one-way. Define h(x) = g(x) with the last bit truncated. h() is one-way because you cannot invert h without inverting g(). h() is not collision resistant because for any x, h(x0) = h(x1)