# What is perfect collision-resistence in probability terms?

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.

• Comments are not for extended discussion; this conversation has been moved to chat. – e-sushi Aug 7 '17 at 23:01

For any fixed data set, you can spend computation up front on the data set to construct a perfect hash $$h_{\mathcal D}\colon \mathcal D \to \{0,1,2,\dots,|\mathcal D| - 1\}$$ which has no collisions, implemented by software such as gperf.

In cryptography, we are seldom worried about random data—we can control keys and choose them randomly and keep them secret, but we usually assume that the adversary has arbitrary control over the data and can choose the most evil, awful, worst-case data imaginable. So there's not much in cryptography to help you with finding a cheaply computed fixed hash function $$h$$ such that $$\Pr[h(d_1) = h(d_2)]$$ is bounded for some distribution on $$d_1$$ and $$d_2$$. There's arbitrarily much heuristic empirical literature on the subject of finding ‘good’ hash functions on particular distributions like English text, like Bob Jenkins' compendium, but that's largely outside the domain of cryptography.

A ‘cryptographic hash function’ like SHA3-256 can be treated as if it were a uniform random function that everybody can evaluate. That may sound like exactly what the doctor ordered for a hash table, and you can use it as a hash for a hash table, and in applications like a distributed hash table or content-addressed storage system open to anyone in the world it may even be essentially the only reasonable kind of choice—but if you take only (say) the low 12 bits as the index into your bucket array or open-addressing array, an adversary can work offline to find lots of 12-bit collisions quite cheaply even if they don't have any shortcuts beyond evaluating SHA3-256. These functions are also not very fast, because there seems to be a high cost to pay for preventing any shortcuts to finding collisions in the whole function, as we discovered the hard way with MD5 and SHA-1.

How can you set a bound on collisions in a secret hash function, e.g. in an application server that has a private in-memory cache, where the hash function need not be shared with the general public?

If you allow $$h$$ to vary randomly, then for any fixed $$d_1 \ne d_2$$, you can have $$\Pr[h(d_1) = h(d_2)] \leq 1/2^n$$; in this case we call $$h$$ a universal hash family, or an $$\varepsilon$$-almost universal hash family if $$\Pr[h(d_1) = h(d_2)] \leq \varepsilon$$, and there are various standard efficiently computed examples (paywall-free: (a), (b)). A typical example in cryptography, for message authentication, is to choose two elements $$r, s$$ at random from a field of about $$2^{128}$$ elements, e.g. $$\operatorname{GF(2^{128})}$$ in GHASH or $$\mathbb Z/(2^{130} - 5)\mathbb Z$$ in Poly1305; interpret 128-bit chunks of a message $$m$$ as coefficients a polynomial in the field; and compute $$h(m) = m(r) + s$$.

You might consider using a universal hash family for a hash table. For a non-adaptive adversary who sends you all input before you operate on it, a universal hash family is a good way to cheaply compute hashes with low probability of collisions. But if the adversary can adaptively submit inputs based on the timing of your past operations, they may be able to discern whether a collision happened and exploit it to make more collisions in a denial of service attack. In applications with an adaptive adversary, you really want a pseudorandom function family like SipHash. More details on universal hash families vs. pseudorandom function families.

Further reading on collision-related metrics in cryptography.

• Thanks. Any reason you didn't meantion SHA1-3? – caveman Feb 20 at 10:12