What is Regular Digest/Hash Function 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' 

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?
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