27
$\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.

Improve this question
$\endgroup$
2
  • $\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
    Commented Jun 19, 2013 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
    Commented Feb 5, 2019 at 0:00

2 Answers 2

Reset to default
20
$\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.

Improve this answer
$\endgroup$
12
  • $\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
    Commented Jun 19, 2013 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
    Commented Jun 19, 2013 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
    Commented Jun 19, 2013 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
    Commented Jun 19, 2013 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
    Commented Jun 21, 2013 at 9:27
5
$\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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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