0
$\begingroup$

This question already has an answer here:

I've been looking through the literature because I want to see if anyone has implemented this idea I have. I know data compression algorithms work by removing redundancy in data. I was wondering though if this scheme I have would work.

Ordinarily the idea of a hashing function $H$ is designed so that $H(x)$ (where $x$ is the message) is easy to compute in the forward direction, but difficult to compute in the reverse direction (computing $H^{-1}(x)$ is intractable). But I also notice another thing about $H$. In practice the length of $H(x)$ is can be as large as 512 bits (I'm referring to the SHA-512 hash). This means that $H$ can map $2^{512} \approx 1.34 \times 10^{154}$ hashes to theoretically an infinite number of pieces of data. It's just that in practice the message space of all possible messages are not necessarily messages that have any meaning to humans. The number of total human readable messages may be on the order of say $2^{520}$ (meaning the total number of unique messages in the entire history of mankind).

So now let us suppose we have a hashing function $h$ which is easy to compute in both directions. We could compress our large data file $D$ into a short hash $h(D)$ that maps to $D$ and several other unintelligible "messages." So now to transmit $D$ all we have to do is to transmit $h(D)$ (which is short) and then the receiver would reverse $h(D)$ until they find a possible intelligent message and they could reconstruct $D$. If such a thing could work it would be possible to compress large amounts of data into short messages.

Does anyone know if such a thing has been done before?

|improve this question
$\endgroup$

marked as duplicate by e-sushi Jul 21 '16 at 6:26

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ How is intelligible defined? $\endgroup$ – mikeazo Jul 20 '16 at 20:20
  • $\begingroup$ Edit: I suppose the MP3 codec could be considered as a variable length hash that is reversible, but an MP3 reverses to exactly one song file. And in order for something to be reversed into one unique piece of data it would have a limit as to how far down it could be compressed. What I am suggesting is that data be encoded as something that is not necessarily unique so that the amount it is compressed can be a lot greater. $\endgroup$ – saribeiro Jul 20 '16 at 20:20
  • $\begingroup$ Mikeazo, intelligible is what I define to be something that maps to a known language, codec or file type. $\endgroup$ – saribeiro Jul 20 '16 at 20:21
  • $\begingroup$ I've been looking through the literature… – and you obviously failed research as you forgot to search sites like this one, or (at least) check on how hash functions work before dropping your duplicate. Long story short: your idea is neither new, nor possible. For specific details, you might want to read the Q&As “Is Checksum to file back decoding possible?” (asked Oct 2013) as well as “Would it be possible to generate the original data from a SHA-512 checksum?” (asked Aug 2015) $\endgroup$ – e-sushi Jul 21 '16 at 6:43
  • $\begingroup$ @mikeazo Just in case you really wonder about that… you can read “intelligible” as if it would say “comprehensible” or “understandable”, while reading “unintelligible” as if it would say “obscure” or “cryptic” or (the term I usually use around here) “enigmatic”. When it comes to definitions, I somewhat disagree when it comes to saribeiro’s personal definition. Providing definitions which are a bit more authorative: “Intelligible” is defined as “able to be understood; comprehensible” (think “clear”), while its antonym “unintelligible” is defined as “impossible to understand” (think “crypted”). $\endgroup$ – e-sushi Jul 21 '16 at 6:59
2
$\begingroup$

The hashing function you describe would be a magical compression method. Well, I'm sorry to burst this on you, but magic isn't real. Magical compression that can take arbitrary data and condense it to a very small size does not exist. In fact, it's easy to prove mathematically that there is no compression method that reduces the size of all data, by the cardinality argument you give.

Compression that reduces the size of common data certainly does exist. But it works by recognizing certain kinds of patterns. Cryptography doesn't help with recognizing patterns — if anything, cryptography is all about hiding patterns.

Compression that can take data among a finite set and condense it to a fixed size is called naming or indexing. Cryptography doesn't help with that either.

|improve this answer
$\endgroup$
  • $\begingroup$ Okay I understand. I don't suppose current compression methods work this way, not even the lossy compression methods. What if though, you could cut the data into blocks and then perform $h(D_{i})$ for each block of data with $i$ ranging from $0$ to $n$ and then find a possible match for just that block? $\endgroup$ – saribeiro Jul 22 '16 at 4:22
  • $\begingroup$ @saribeiro You could do that, but that's even less likely to help: by breaking down data into smaller blocks, you remove the opportunity for compressing common kinds of data by recognizing repetitive patterns across blocks. $\endgroup$ – Gilles 'SO- stop being evil' Jul 22 '16 at 6:50

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