Motivation. When I use a hash function, I would like my pre-images (original values) to a given output (hash) to be evenly distributed as it could be that an uneven distribution could make guessing / checking for original values easier.

Mathematical formulation. We can regard a hash function as a surjective map $h:\mathbb{N}\to F$ where $F\subseteq \mathbb{N}$ is a finite set. We say that $h$ is fair if $$\lim_{n\to\infty} \frac{|h^{-1}(b)\cap\{1,\ldots,n\}|}{n} = \frac{1}{|F|}$$ for all $b\in F$.

Another natural notion of "fairness" is the following: a hash function is weakly fair if $f^{-1}(\{f(x)\})$ is infinite for all $x\in \mathbb{N}$, that is for every hash there are infinitely many possible inputs (original values).

Question. Is it known for any of the currently used cryptological hash functions whether it is (weakly) fair?

  • $\begingroup$ Anyway, check out the sponge construction which I think is the easiest to analyze real-world crypto that has this property (if we ignore padding, $n$ not being a multiple of block sizes, etc). Or at least derives it starting from a "fair" permutation. $\endgroup$
    – orlp
    Commented Dec 25, 2020 at 17:57
  • 2
    $\begingroup$ My guess is that very little can be unconditionally proven about cryptographic hash functions used in practice, but cryptographers tend not to care; they're used to this. Rather, cryptographers tend to focus on what can be proven under reasonable assumptions. Normally hash functions are one of the primitive building blocks that we have to make assumptions about (e.g., that the hash function is good in some way). Perhaps you might consider editing the question to add some motivation. $\endgroup$
    – D.W.
    Commented Dec 28, 2020 at 21:14
  • 2
    $\begingroup$ A related concept is a regular function, as defined by Goldreich, Krawczyk and Luby. Informally: "[in] regular functions, ... every image of a $k$-bit string has the same number of preimages of length $k$." Formally, per Definition 2 of the paper: "A function $f$ is called regular if there is a function $m(\cdot)$ such that for every $n$ and for every $x \in \{0, 1\}^n$ the cardinality of $f^{-1}(f(x)) \cap \{0, 1\}^n$ is $m(n)$." $\endgroup$ Commented Dec 29, 2020 at 9:17
  • $\begingroup$ Thanks @D.W. - I added motivation, and a concept of "weak" fairness $\endgroup$ Commented Jan 8, 2021 at 10:37
  • 1
    $\begingroup$ Thank you for the motivation. I can now respond to your motivation. The answer is: we already need to assume that our hash functions are one-way, preimage-resistant, etc. -- i.e., that given an output, it is hard to guess a preimage. That's a much stronger assumption. So, we don't really care that we can't prove the weaker notion ("fair"), since we're already assuming something that is both morally stronger and is what we actually need/care about. To work in cryptography, one must get comfortable with relying on unproven assumptions. $\endgroup$
    – D.W.
    Commented Jan 8, 2021 at 20:47


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.