1
$\begingroup$

It is well known that the birthday paradox suggests that finding collisions in an n-bit hash function requires about $O(2^{n/2})$ evaluations. This heuristic underlies the common assumption that collision resistance scales with the square root of the output space size.

Question: For hash functions constructed from a secure pseudorandom permutation (using standard designs such as Davies–Meyer or Miyaguchi–Preneel):

  • Do we have formal lower bounds proving that no generic collision-finding algorithm can asymptotically beat the $O(2^{n/2})$ bound?
  • Or is the birthday bound only a heuristic, without any unconditional proof of optimality?

I am trying to clarify whether a rigorous proof exists in the standard model, or if the birthday bound should only be regarded as a rule of thumb.

$\endgroup$
4
  • $\begingroup$ I doubt you can prove the birthday attack is optimal. Collision analysis on cryptographic hash functions have yielded faster algorithms, typically by finding ways of improving a raw birthday attack using knowledge of the specifics. There may be no known faster algorithm than a birthday attack on a particular hash function, but that doesn't mean one does not exist. $\endgroup$ Commented Aug 17 at 10:32
  • $\begingroup$ I see your point. Then is it correct to say that, outside of idealized models (like the random oracle), we cannot hope for unconditional lower bounds at all, since structural properties of specific constructions may always allow improvements over the birthday bound? $\endgroup$ Commented Aug 17 at 14:52
  • $\begingroup$ 'may always' gets you out of jail. If you just say 'always', you need to prove it. Good luck with that :) $\endgroup$ Commented Aug 17 at 15:39
  • $\begingroup$ By saying “may always,” I intend to capture the possibility that specific constructions could allow improvements, without asserting an unconditional lower bound. This distinction is important to highlight the difference between heuristic and provable results. $\endgroup$ Commented Aug 17 at 17:36

0

Reset to default

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.