# Is there a hash function which has no collisions?

Is there a hash function which has no collisions?

To clarify: it would be some function which would produce variable-length output, and never produce the same output for differing input. It would also be computationally hard to derive the input from the output.

• There are collision free one way functions. For example $y = g^x \mod p$. But I'm pretty sure that SHA-512 would be a better choice, despite the collisions. Jun 19, 2013 at 5:53
• @CodesInChaos How is this collision free? If we consider all the possible inputs of ⌊²log(p)⌋+1 bits, then by definition there will be at least one collision amongst them? Feb 5, 2019 at 0:00

Your hypothetical hash function would need to have an output length at least equal to the input length to satisfy your conditions, so it wouldn't be a hash function. See the Pigeonhole principle.

Remember an n-bit hash function is a function from $\{0,1\}^∗$ to $\{0,1\}^n$, no such function can meet both of your conditions. Essentially, if it has length $n$ bits, it can only guarantee uniqueness for inputs up to $n$ bits, and even then it would not be a good PRF as it would be a permutation - which is not what hash functions are - so you would want the output size to be longer than the input size, which is now really far from the definition of a hash function.

Now, if you are willing to call it something else than a hash function, then, yes, it is possible to construct such primitives, under the assumption that the output length must be calculated in a way that if there are $m$ possible inputs for an $n$-bit output, then $m \leq 2^n$. The obvious one is a block cipher, which satisfies your conditions except that it has the additional property that all outputs have a corresponding input, which may not be what you want.

As you can see, if you don't want a permutation, you are basically left with a function which "expands" the input pseudorandomly, such that all inputs have outputs but not all outputs have inputs. For instance, CodesInChaos's example of $y = g^x \mod{p}$ is collision-free if $|X| \leq p$ where $X$ is the set of inputs to the function and is one-way for sufficiently large prime $p$ (actually, it needs to have a subgroup of large order, generally $p = 2q + 1$ is a common choice for large prime $q$), as you would need to solve the discrete logarithm problem to reverse it.

• I understand that the output would need to be longer than the input, I was thinking of a function that one would use to prove possession of data that they would release at a later date, to prove they had the data at least that far back.
– benj
Jun 19, 2013 at 5:31
• @improv32 Hash functions can do that in what is called a commitment scheme. Why do you require the "no collision" property? Or did you really mean, "with a negligibly low chance of collision, which then is what cryptographic hash functions are for in that while there are infinitely many collisions, it is very hard to find one either accidentally or on purpose"? Jun 19, 2013 at 5:33
• I was just curious if there was a function which did not have negligible chance of collision, but provably has no collisions.
– benj
Jun 19, 2013 at 5:58
• @improv32 I understand. No, there isn't, under the standard definition of "hash function". But there are certainly one-way, collision-free functions, as CodesInChaos mentioned in a comment. Jun 19, 2013 at 6:04
• @improv32: Just use any encryption scheme you like with a key much shorter than the data. (You can easily remove this requirement if needed.) To later prove you had the data earlier, release the key you encrypted it with. Jun 21, 2013 at 9:27

Yes they are called Perfect hash functions on wiki iv also seen them being called collision free hash functions. If you follow the link at the bottom of the page there are links to articles and source code.

• Perfect hash functions are not cryptographic hash functions as their domain is finite. Jan 5, 2015 at 15:01
• @Thomas what does it mean "a finite domain"? Sep 18, 2015 at 18:23
• A finite domain would mean that the number of possible outputs is finite. I.e. that there is some integer N so that the function has at most N different possible outputs. Which is mutually exclusive with having no collisions, because you can always generate N+1 different inputs (for example, text files containing the numbers 1, 2, 3, ... N+1) and because there are only N possible outputs, there will be at least one collision amongst them. Feb 4, 2019 at 23:35
• Actually, the right term should be codomain rather than domain. Domain refers to the input space of a function, and codomain to its output space. Feb 4, 2019 at 23:39