# Weak and strong uniformity of cryptographic hash functions

For any $$n\in\mathbb{N}$$, let $$\{0,1\}^n$$ denote the set of $$\{0,1\}$$-strings of length $$n$$. For $$n\in\mathbb{N}$$ let $$\{0,1\}^* = \bigcup_{k\in\mathbb{N}}\{0,1\}^k \text{ and } \{0,1\}^{\leq n} = \bigcup_{k\leq n}\{0,1\}^k.$$

Note that $$|\{0,1\}^{\leq n}| = 2^{n+1} -1$$.

Cryptographic functions $$h$$ map $$\{0,1\}^*$$ to $$\{0,1\}^n$$ for some fixed $$n\in\mathbb{N}$$. Note that in general, for a cryptographic hash function $$h:\{0,1\}^*\to \{0,1\}^n$$ it is not known whether $$\text{im}(h) = \{0,1\}^n$$ where $$\text{im}(h) = \{h(x): x\in\{0,1\}^*\}$$ is the image of $$h$$.

1. A cryptographic hash function $$h:\{0,1\}^*\to \{0,1\}^n$$ is said to be weakly uniform if for every hash value there are infinitely many collisions, i.e. $$h^{-1}(\{h(x)\})$$ is infinite for every $$x\in\{0,1\}^*$$. (The pidgeonhole principle only implies the existence of one $$x\in\{0,1\}^*$$ such that $$h^{-1}(\{h(x)\})$$ is infinite.)

2. A cryptographic hash function $$h:\{0,1\}^*\to \{0,1\}^n$$ is said to be strongly uniform if the number of pre-images for each possible hash value approaches $$1/|\text{im(h)}|$$ as the input length grows longer, or, formally, if for every $$x\in \{0,1\}^*$$ we have: $$\lim \sup_{n\to\infty} \frac{|h^{-1}(\{h(x)\})\cap \{0,1\}^{\leq n}|}{2^{n+1}-1} =\frac{1}{|\text{im}(h)|}.$$

Question. Of all the hash functions known to be cryptographically secure, is there one of which we know whether it is weakly, or even strongly, uniform?

If we look at more mathematically structured hash functions which use ideas from public key cryptography such as the Chaum-van Heijst-Pfitzmann Hash Function (see section 7.4 of Stinson Cryptography: Theory and Practice), we can reduce the output modulo $$2^n$$ and have weak uniformity by the surjectivity of powers of primitive roots. Moreover, if $$p-1$$ is divisible by $$2^n$$ then we will have strong uniformity.