Why can't we use a hash with no collision to compress data reliably?

Question

According to wikipedia, a hash maps digital data of arbitrary size to digital data of fixed size.

For all practical measures, a hash is a unique signature of a big chunk of data. But there is such a thing as a collision free hash, I "heard".

Other than being able to decompress back, arguably the main difference between compressing and hashing is precisely that collision factor - but what if the hash has no collisions?

Why exactly can't we "just" get that "perfect" hash and use it as a compressing method instead? Wouldn't it be able to generate way smaller files?

^{I see how I must be just missing something, so it's just my way of trying to understand what's the underlying difference between hashing and compressing! :)}

Answer 1

Mathematically speaking, there is no such thing as a collision-free hash. Practically speaking, there is.

Cryptographic hash functions in good standing have no known collisions. That's one of their defining properties. They do have collisions, but there isn't enough computing power on Earth (if not in the whole universe) to find one, given current mathematical knowledge. A SHA-1 value is 160 bits, so we know that there exists a pair of 161-bit strings that have the same hash, but the best-known techniques to find one are out of range of current computing power (not out of range of imaginable computing power, though, which is why we're moving away from SHA-1).

Intuitively speaking, if it's hard to find collisions for a hash, the hash is hard to inverse. If there was a known algorithm to invert a hash, then at some point the algorithm would have to decide which of the possible preimages to go for, and we could run it with both decisions to find a collision.

It is possible to use a hash as a compression function. But since there is no way to calculate the original text from the hash, this compression method can only be used when the original text is available. Sounds useless? Not quite. In fact, that's one the basic reasons to use hashes! Cryptographic hashes are used when there are two storage or communication mechanisms, one that's secure but supports only a small volume of data, another that's insecure but supports a large volume of data. Store the hash on the small, secure storage and the actual data on the large, insecure storage. Then, when you need the file, retrieve the data, retrieve the hash, and check the hash. In this way, the secure storage mechanism uses the hash as a compression function; the decompression function makes use of the insecure storage, but guarantees the security of the outcome. (You'll not that something is lost, however: if the insecure storage is corrupted, this will be detected, but cannot be corrected. The “decompression” mechanism guarantees integrity (if you get the data back, it's the right data) but not availability (you might not be able to get the data back).)

Seen another way, a cryptographic hash can be used as a compression mechanism, but this requires that each time a new file is stored, the decompression function is somehow modified to remember the original file content. This is clearly impractical, but it is of theoretical interest — this basically describes a random oracle, which is a sort of idealized version of a cryptographic hash.

A perfect hash is a different kind of beast: it is mathematically collision-free, but it achieves that by restricting the possible inputs to a finite (usually small) subset of all possible inputs. The decompression function for a perfect hash is usually stored as a table from hash values to the corresponding original data (for example using an array if the hash values are small integers).

Answer 2

A perfect hash function computes unique indexes for a predefined finite set of possible inputs. Typically such a function is used to implement a hash table. It is then not necessary to worry about collisions. Normally the set of possible inputs is small and known, such that it is also possible to invert the function (i.e., given the index one can find the input).

Example: If you have the set of strings

("Hello World", "A quick brown fox", "A lazy dog")

then for example the function counting the occurences of character l in a string would be a perfect hash function for those strings, as it would map the strings to indexes as follows:

"Hello World" -> 3
"A quick brown fox" -> 0
"A lazy dog" -> 1

So you can somehow use this function for compression. However there are a number of problems:

1) A first potential problem is that in order to decompress you must know the perfect hash function and the set of possible strings. So if you store '3' in a file you also have to store somewhere the fact that '3' corresponds to "Hello World". This approach can however make sense if you have a fixed set of inputs that you use for many files.

2) You will only have a compression if you have a small set of large inputs. E.g., if the set of possible inputs is {"a","b",...,"z"}, then the resulting indexes (hashes) will be like {1,...,26} an no compression takes place. So this hashing is not suited for general purpose compression.

3) Mapping every input to the same fixed size index may not be the best idea for compression. General purpose compression functions like Huffman coding also consider the probability of occurence of the different strings, and then strings that occur more often are mapped to shorter sequences than very rare strings, which gives a better compression ratio.

PS: Your question is not really a cryptography question, as perfect hash functions for hash tables are not cryptographic hash functions.

Answer 3

Using a perfect hash in this case is essentially the same as using an index. For a perfect hash to work, both the compressor and decompressor have to know the $N$ possible things that might be "compressed" in the data.

You are better off giving them each a number in $[0,N)$, and using $log_2N$ bits as your "compressed data".

This is better than a perfect hash because it uses the minimum number of information possible (perhaps not true with a perfect hash), and doesn't give any more information about the contents than a hash does.

The only way a perfect hash would be better would be if you didn't want other people knowing how many possible items there were. The hash comes from a larger number space, so people can't very easily see if there are only 5 items, or 500 million items.

Answer 4

If you have enough computing power to crack a hash, you can send big files over the internet almost instantly, reducing the need for expensive and powerful network infrastructure, you would have to crack it faster than it takes to download the file to be worth it at least time wise, it may be physically, economically and technologically inefficient or even impossible to have a smartphone/computer the same size and price you have but fast enough to be able to crack hashes like a supercomputer can, or even every supercomputer on earth and universe combined can't. If you find a way to crack hashes instantly with a portable quantum computer for example, then it would be a good way to reduce network load and make the internet almost instantaneous or you can find a way in the middle that you would be able to compress files using more than a hash, perhaps a hash and many parameters in a text file, to guide the cracking algorithm the right way, in password cracking for example it takes a very long time to bruteforce a password when you have absolutely no information about the length or character set of the password, but if only you had the length and character set of the password it would significantly reduce the time used to crack the hash.The same thing could be done with larger files/information.Here is a small example :

Hash and parameters : sha1: 19f054f1f448ff152f1d586be39a56f179fe80c9 Lowercase letters only : yes Words in a dictionary : yes Length : 13

Result : stackexchange