2
$\begingroup$

In my cryptography class, the professor said that collision resistance for a fixed hash function is not a "precise" definition. The reason is since a fixed hash function is a single instance of a computational problem it can't be hard(at least for a somewhat precise and complete definition of collision resistant). Note that it is not said that we know solutions for a fixed hash function. However, the definition seems to make more sense for a family of hash function. So this is more of a theoretical question than "in practice".

How would you explain this differently?

$\endgroup$
1

1 Answer 1

3
$\begingroup$

To define collision-resistance for a fixed hash function $H$, it probably looks like this:

CR: There is no efficient attacker (i.e., with polynomial computational resources) that can find two messages $m_0\neq m_1$ such that $H(m_0)=H(m_1)$ with non-negligible probability.

However, this is problematic because such an attacker may indeed exist but we just cannot find it easily. From the pigeonhole principle, we know for sure that there are two colliding messages for $H$. So, there exists a very efficient attacker who can simply output these two messages and break the above security.

To deal with this issue, one may attempt to rephrase CR as "It's hard to construct an attacker...". But then you got stuck on defining "hard to construct" formally, while in practice this is OK.

So, an easy fix is to introduce a large key space $K$ such that it's hard for any efficient attacker to output colliding messages for a randomly-chosen hash function $H_k$ (where $k\gets K$). Note that even if the attacker is given all colliding messages for all keys, it cannot "digest" them easily compared to the case with a fixed hash function because storing all colliding messages requires exponentially-large space (linear to the size of the key space) while the attacker has only polynomial computational resources.

$\endgroup$

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.