15
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – CodesInChaos Jun 19 '13 at 5:53
  • $\begingroup$ @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? $\endgroup$ – RocketNuts Feb 5 at 0:00
14
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – benj Jun 19 '13 at 5:31
  • $\begingroup$ @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"? $\endgroup$ – Thomas Jun 19 '13 at 5:33
  • $\begingroup$ I was just curious if there was a function which did not have negligible chance of collision, but provably has no collisions. $\endgroup$ – benj Jun 19 '13 at 5:58
  • $\begingroup$ @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. $\endgroup$ – Thomas Jun 19 '13 at 6:04
  • 3
    $\begingroup$ @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. $\endgroup$ – David Schwartz Jun 21 '13 at 9:27
3
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Perfect hash functions are not cryptographic hash functions as their domain is finite. $\endgroup$ – Thomas Jan 5 '15 at 15:01
  • $\begingroup$ @Thomas what does it mean "a finite domain"? $\endgroup$ – cregox Sep 18 '15 at 18:23
  • $\begingroup$ 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. $\endgroup$ – RocketNuts Feb 4 at 23:35
  • $\begingroup$ 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. $\endgroup$ – RocketNuts Feb 4 at 23:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.