Distinguishing cryptographic properties: hiding and collision resistance

Question

I saw from Another question the following definitions, which clarifies somewhat:

Collision-resistance:

Given: $x$ and $h(x)$

Hard to find: $y$ that is distinct from $x$ and such that $h(y)=h(x)$.

Hiding:

Given: $h(r|x)$, where $r|x$ is the concatenation of $r$ and $x$

Secret: $x$ and a highly-unlikely-and-randomly-chosen $r$

Hard to find: $y$ such that $h(y)=h(r|x)$.

This is different from collision-resistance in that it doesn’t matter whether or not $y=r|x$.

My question:

Does this mean that any hash function $h(x)$ is non-hiding if there is no secret $r$, that is, the hash is $h(x)$, not $h(r|x)$?

Example:

Say I make a simple hash function $h(x) = g^x \pmod n$, where $g$ is the generator for the group. The hash should be Collision resistant with $$p(x_1 \ne x_2, h(x_1) = h(x_2)) = \frac{1}{2^{\frac{n}{2}}}$$ but I would think it is hiding as well?

Answer 1

• Pre-image resistant: given a hash value $h$ find $m$ such that $h=Hash(m)$. Consider storing the hashed of password on the server. An attacker will try to find your password.

• Second Pre-image resistant: As Henno Brandsma said this is also called collusion resistant means. In this case, the attacker wilt try to find and $h'$ such that $h' = Hash(m)$. Note that; $h'$ can be equal to $h$.

• Hiding: This technique due to Time-Memory attack on Block cipher by Hellman and Hash Functions. Modern from, Rainbow Tables, is due to Oechslin. To mitigate the attacks, one solution is concatenating a random value to passwords, called salt. So the $h=Hash(r|m)$ is stored in the database with the salt. Now, the attacker must have to build a new table for any of the password in the database. Finding an $m'$ s.t $Hash(m') = Hash(r|m)$, in this case, will not solve the problem. Because the server will calculate $Hash(r|m') \neq Hash(r,m)$.

  Adding salt (or in general random value), in Cryptography, has many applications.

The answer to your question; yes, it is not hiding, because there is no random. For some applications, non-hiding will be enough, as comparing the hash of the download with hash from the server to see that the download is complete.

I assume that the $g$ generates a cyclic group;

If the two elements are unique, yes the hash will be different. In general, however, one must support larger values than the group size. such two values $x_1 = x_2 + k \bmod m$ will have collision. To hide it, you must add random value.