update: removed lots of stupidity... sorry. I didn't know I can be this stupid but I achieved it.
1. Goal
Let $\mathcal{D}$ be the universal space of our plain data. Our goal is to find a function $h:\mathcal{D} \rightarrow \{1,0\}^n$ where $n$ is some positive constant, such that:
- For any $d_1,d_2 \in \mathcal{D}$, the probability that $h(d_1) = h(d_2)$ is $1/2^n$. I.e. it's very unlikely to have collisions.
Note 1: the reason I require the probability to be $1/2^n$ is because I think this is the minimum possible collision probability. I would also appreciate if anyone could correct me on this.
2. Questions
- Is $1/2^n$ the minimum achievable probability for collisions on any dataset?
- Any of my methods are perfect for any dataset? I.e. not just best on average, best on specific datasets as well.
- Can you propose one that is perfect on all dataset? (would be great if you can describe it in probability terms too).
3. My attempt
Let $z:\mathcal{D} \rightarrow \mathcal{Z}$ be a function such that for any $d\in\mathcal{D}$:
- There is a function $u$ such that, for any $d\in\mathcal{D}$, $u(z(d)) = d$.
- $\texttt{len}(z(d)) = H(d)$ where $\texttt{len}(z(d))$ is number of bits in $z(d)$ and $H(d)$ is Shannon's entropy of $d$.
I.e. $z$ is a perfect lossless compression function.
Ideally, we wish if $\texttt{len}(z(d)) \le n$ is always achievable. This way we can use $z$ as a perfectly collision-free implementation of $h$.
But in reality we can't do that as some input $d$ could contain too much information to be represented losslessly in $n$ many bits.
For simplicity, we will assume that, for any $d \in \mathcal{D}$, $\texttt{len}(z(d)) \ge n$.
This way, if the perfect compression function $z$ is known, then finding the perfect collision-free hashing function $h$ is a matter of choosing which of the bits in $z(d)$ to be kept in $h(d)$.
The process of deciding which bits to be kept in $h(d)$ needs to only satisfy:
- For any $d_1,d_2\in\mathcal{D}$, probability of $h(d_1)=h(d_2)$ must be kept $1/2^n$.
- The process must be producible. So computing $h(d)$ now should give us the same output if we compute $h(d)$ later on in the future.
3.1. Choosing $n$ bits method 1
For any $d\in\mathcal{D}$, assume that the early bits in $z(d)$ are more important than the latter bits in helping us set $d$ apart from others in $\mathcal{D}\setminus\{d\}$.
Therefore, since early bits are most important, we just choose the first $n$ bits. I.e. $h(d) = z(d)[1:n]$, where $z(d)[1:n]$ denotes to the first $n$ bits in $z(d)$.
Note 4: I implemented this in Python here (in case one day someone [me included] wishes to evaluate these hashes against others to see how bad they are).
3.2. Choosing $n$ bits method 2
Unlike method 1, here we assume that any bit is equally important to any other bit. So instead of choosing the first $n$ bits in $z(d)$, we choose the $n$ bits randomly from $z(d)$. In order to make this reproducible, we seed the random selection by $z(d)$ itself.
In Python-inspired notation, it looks like this:
- First we set the seed of the PRNG $\texttt{random.seed}(z(d))$.
- Then we $z_{\texttt{shuffled}}(d) = \texttt{random.shuffle}\big(z(d)\big)$.
- Finally $h(d) = z_{\texttt{shuffled}}(d)[1:n]$.
Note 5: in my view if $z$ and the PRNG used in the random shuffling are perfect, then this method is a perfect collision-resistant hashing function under this assumption which states that all bits in $z(d)$ are equally important.
Note 6: I have coded this in Python and it can be found here.