Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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.

share|improve this question
    
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. –  CodesInChaos Jun 19 '13 at 5:53
add comment

1 Answer 1

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.

share|improve this answer
    
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. –  improv32 Jun 19 '13 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"? –  Thomas Jun 19 '13 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. –  improv32 Jun 19 '13 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. –  Thomas Jun 19 '13 at 6:04
2  
@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. –  David Schwartz Jun 21 '13 at 9:27
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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