I was reading a paper, Practical and Provably-Secure Commitment Schemes from Collision-Free Hashing where there was a reference to message digests being 'regular' snippet of paper

Here, MD is a message digest. I've not been able to find anything online about the regular property of message digests/hash functions. Does anyone here know about it?

  • $\begingroup$ Have you tried emailing the authors? $\endgroup$ Sep 24 '19 at 16:55
  • $\begingroup$ Since its an old paper, I didn't think of doing it $\endgroup$
    – TdBm
    Sep 25 '19 at 9:52
  • The first Cryptography textbook implicitly containing word regular for hash functions may be in Stinson's book Cryptography Theory and Practice, First Edition, 1995, around pages 234-237. T

    Since we are interested in a lower bound on the collision probability, we will make the assumption that $\mathbf{h^{-1}(z) \approx m/n}$ for all $\mathbf{z \in Z}$. (This is a reasonable assumption: if the inverse images are not approximately equal, then the probability of finding a collision will increase.)

    Stinson's book is pointed out by Bellare and Kohno's article,

    Stinson, in the first edition of his book, shows that Equation (1) is true under the assumption that $h$ is regular. There is no information regarding the case where $h$ is not regular.

  • This term is not defined in Practical and Provably-Secure Commitment Schemes from Collision-Free Hashing, 1996

    Of course, the latter attack can be prevented if $\text{MD}$ has additional properties besides being collision-free (e.g., if MD is “regular”).

    Only mentioned as an additional requirement for the hash function.

  • This definition from Hash Function Balance and its Impact on Birthday Attacks, 2004, by Bellare and Kohno

    Textbooks tell us that a birthday attack on a hash function $h$ with range size $r$ requires $r^{1/2}$ trials (hash computations) to find a collision. But this is quite misleading, being true only if $h$ is regular, meaning all points in the range have the same number of pre-images under $h$; if $h$ is not regular, fewer trials may be required.

A brief result from the Bellare and Kohno's article;

Let $C_h(q)$ be the probability that the birthday attack on a hash function $h: D \to R$ succeeds in finding a collision in $q$ trials.

With balance measurement $\mu$ and up to constant factors

$$C_h(q) = \binom{q}{2} \frac{1}{r^{\mu(h)}}.$$

A collision expected with $r^{\mu(h)/2}$ trials.

  • $\mu(h) = 1$ meaning that $h$ is regular and this is standard birthday collision.
  • $\mu(h) = 0$ meaning that $h$ is a constant function so attack has $\mathcal{O}(1)$

This, actually indicates that the values are between regular and constant function. If the balance $\mu(h) =1/2$ than a collision can be found in $r^{1/4}$ trials, less than $r^{1/2}$

Result: If a hash function is not regular, finding a collision is easier than regular hash functions.

Bold in quoted text are mine

  • $\begingroup$ I found this definition in How to Build a Hash Function from any Collision-Resistant Function "Regularity. A function is regular if each image has an equal number of preimages." . Is it the same meaning as what you have explained @kelalaka? $\endgroup$
    – TdBm
    Sep 25 '19 at 9:58
  • $\begingroup$ @TdBm yes they are same. Just different wordings. Note that Stinson doesn't define regular, however, Bellare mention's Stinson's theorem in the textbook usages. $\endgroup$
    – kelalaka
    Sep 25 '19 at 10:29
  • 1
    $\begingroup$ Thank you @kelalaka $\endgroup$
    – TdBm
    Sep 29 '19 at 17:09
  • $\begingroup$ @TdBm Welcome. I'll delete my comment. $\endgroup$
    – kelalaka
    Sep 29 '19 at 17:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.