<p><strong>Motivation.</strong> 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.</p>
<p><strong>Mathematical formulation.</strong> We can regard a hash function as a surjective map <span class="math-container">$h:\mathbb{N}\to F$</span> where <span class="math-container">$F\subseteq \mathbb{N}$</span> is a finite set. We say that <span class="math-container">$h$</span> is <em>fair</em> if <span class="math-container">$$\lim_{n\to\infty} \frac{|h^{-1}(b)\cap\{1,\ldots,n\}|}{n} = \frac{1}{|F|}$$</span> for all <span class="math-container">$b\in F$</span>.</p>
<p>Another natural notion of &quot;fairness&quot; is the following: a hash function is <em>weakly fair</em> if <span class="math-container">$f^{-1}(\{f(x)\})$</span> is infinite for all <span class="math-container">$x\in \mathbb{N}$</span>, that is for every hash there are infinitely many possible inputs (original values).</p>
<p><strong>Question.</strong> Is it known for any of the currently used <a href="https://en.wikipedia.org/wiki/Cryptographic_hash_function" rel="nofollow noreferrer">cryptological hash functions</a> whether it is (weakly) fair?</p>

CC BY-SA 4.0
2020-12-25T17:57:18.400Z
Anyway, check out the [sponge construction](https://en.wikipedia.org/wiki/Sponge_function) 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.
orlp
CC BY-SA 4.0
2020-12-28T21:14:41.003Z
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.
D.W.
CC BY-SA 4.0
2020-12-29T09:17:32.163Z
A related concept is a *regular function*, as defined by [Goldreich, Krawczyk and Luby](https://epubs.siam.org/doi/pdf/10.1137/0222069). 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)$."
Sadeq Dousti
CC BY-SA 4.0
2021-01-08T10:37:20.960Z
Thanks @D.W. - I added motivation, and a concept of "weak" fairness
Dominic van der Zypen
CC BY-SA 4.0
2021-01-08T20:47:11.983Z
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.
D.W.
CC BY-SA 4.0
2021-01-08T22:12:59.960Z
Thanks @D.W. about this comment, especially about the concept of the reliance on unproven assumptions
Dominic van der Zypen
<cr.crypto-security><hash-function>
"Fair" hash functions
Dominic van der Zypen
# "Fair" hash functions

(Asked by: username_0 on 2020-12-25)

**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](https://en.wikipedia.org/wiki/Cryptographic_hash_function) whether it is (weakly) fair?

**Tags:** cr.crypto-security, hash-function
> **Comments:**
> **username_1**: Anyway, check out the [sponge construction](https://en.wikipedia.org/wiki/Sponge_function) 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.  
> **username_2**: 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.  
> **username_3**: A related concept is a *regular function*, as defined by [Goldreich, Krawczyk and Luby](https://epubs.siam.org/doi/pdf/10.1137/0222069). 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)$."  
> **username_0**: Thanks @D.W. - I added motivation, and a concept of "weak" fairness  
> **username_2**: 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.  
> **username_0**: Thanks @D.W. about this comment, especially about the concept of the reliance on unproven assumptions  

---

## 0 answers

