3

I'm a high school student interested in topics of computer programming.
Recently I became interested in file compression, and in my head I tried to combine this with a completely different part of programming I heard about a while ago, hash values.

From my understanding the hash value of a file is created by an algorithm which performs a one-way secure function on the contents of the file, to output a code or tag of a given length.
Would it be possible to create a reversible non-secure hash value generator, which would create a value for a file to be compressed, along with hash values for simple variations of the file (such as missing a few characters), and then feed those values along with the given file's length to a program that would through trial and error attempt to construct a file that fit the criteria of the variating hash values?

I know that this would be EXTREMELY resource-intensive on a computer to decompress, but would it be possible? And depending on the nature of the value generator, could there be a way to narrow the range that the answer is found in so as to make it easier on the computer?

1

Information Theory

Now an N bit-vector can represent 2^N possible states. It is possible with fore knowledge to assign each state to a single valid document of any length. In this sense there is no lossyness, all valid documents can be clearly communicated in the smallest amount of space. There is no encoding scheme that can squeeze any more meaning into a N bit vector. Whatever the length that you peg that vector at dictates how many valid documents you can get. This is a fundamental property of Entropy. I highly recommend reading Claude Shannon's paper on Information Theory. It will take some time to digest.

Perfect Compression

But to your question. Can you somehow drop half (more or less) of the bits in the compressed representation and still extract the document? Yes, and No.

Lets say that K bits were dropped from the message. This is the same as saying that there was noise during communication that obscured the state of those bits. Given only the bits that you received, can you discover the original message?

If this message was perfectly compressed, those missing bits introduced (2^K)-1 other valid documents. These documents are equally valid, and equally expected as the intended document. The receiver can only generate each possibility and say "One of these".

Now that does not mean that the receiver is completely confused. If all of the possible documents have the same property, say the titles are identical, or the timestamps agree on the date etc... Then the receiver can act on that information. On the other-hand, the receiver will need to be more cautious about contradictory properties, and about the validity of an action given the uncertainty in the message.

Tolerating Imperfection

It would be nice if the receiver could dismiss all the (2^K)-1 documents and recover the one true message. But for this to happen the compression scheme has to be less than perfect. Essentially we have introduced at least (2^K)-1 invalid states into the compressed output. This is actually the basis for Self-Healing codes, error mitigating codes, and error detecting codes. I'm not going to go into specifics about how these encodings work on a bit by bit level but think of them as levels of protection.

  • An error detecting code like a hash, or cyclic-redundancy checksum (CRC) allows the receiver to verify that everything was received as sent to some level of confidence 1 / (2^(C+N)) bits where C are the number of bits in the hash/crc. They may also provide some limited diagnostics as to what went wrong. And paired with an exploration of the bit space suggest potentially valid documents.
  • An error mitigating code like a grey-code, is assembled in such a way that an error in some K bits only changes the meaning of the message by at most (+/-)cK values off (c being a constant). These are best with continuous values such as frequencies for music, or degrees of rotation or temperature where being a little off is not a serious issue.
  • An error correcting code allows the exact valid document to be recovered when anywhere up to K error bits have occurred. Past that K bits though it devolves into an error detecting/mitigating code.

Regeneration with just a Hash

In this case the hash is serving as an error detecting code. Unfortunately all N bits of the message have been lost. It is possible to enumerate all bit sequences from n..N bits long, and either compute their hash to verify their validity, or construct the enumerator such that it can only produce valid bit sequences algorithmically. The receiver would need to guess the range of n..N such that the valid message was generated.

Guessing the n..N bit range might be assisted by encoding the length somehow in the hash. Allowing somehow to prove that messages with less than n bits or more than N bits will always be invalid. This will make the Hash function much poorer as a hash of the contents, as it will focus more on a documents length. This will allow the generator to target a specific n..N bit range, but at the cost of recognising more of those bit vectors as valid documents.

Notice though that for this to work as a true compression algorithm, the hash could never have a collision with another valid document. That means there is one unique hash state for each valid document. Which makes the hash the compressed document, just a very hard to decode document. Unfortunately a Hash without collisions is hard to engineer, and usually requires more bits than the original message, making it more of a diffusion than a compression technique. Conversely if collisions are allowed the Hash devolves back toward error mitigating, or error checking depending on how close the valid documents are in terms of meaning.

So Yes, you can send a hash through and the receiver can extract the original message, at great expense of effort.

But No the receiver will also receive a lot of other unintended messages too.

10
  • Ok so to make sure I understand, it is possible, but the larger the file the more duplicate possibly correct files I will have to go through to find the original, and if I change the hash function to factor in length, it will also make the function less reliable by allowing more duplicates? An algorithm with no collisions would mean one that created a hash only that given file can make, but it would take as much space to store the hash as it would the file. So the lower quality hash fnction I use, the more duplicates, but I would also gain the benefit of getting a smaller size value to store. – Goel Nimi Dec 31 '18 at 16:16
  • @GoelNimi Think of a hash like a thumbnail of a picture, each thumbnail has the same height and width. A thumbnail of a large ship would look identical to a thumbnail of a scale model of the ship. If you were to add someway to calibrate for scale (document length) you necessarily obscure a portion of ship by covering it up or shrinking the relative size/count of features notable in the thumbnail. The portion that falls into obscurity makes essentially different images appear identical. – Kain0_0 Jan 2 '19 at 2:23
  • @GoelNimi The hash size to original size is not actually fixed. It depends on the set of valid messages. If you have a set of 8 valid 2gb messages, you can encode that in 3bits. 3bits is the smallest the hash could possibly be to encode all messages equally small without collision. Similarly a dense message set of (2^N) N bit messages will take 2^N bits to encode without collision. These are minimums though. Usually a hash is defined over all Bit vectors from 0.. so it will require infinite space to store a collision-free representation. – Kain0_0 Jan 2 '19 at 2:47
  • @GoelNimi You should always use a good quality hash function. There is no reason not too. Of course a lower resolution hash value (a value with fewer bits) will have more collisions. As the number of collisions increases so too does the chance that a hash value represents more than one valid message. – Kain0_0 Jan 2 '19 at 3:06
  • You said that it would require an infinite space to store a collision-free hash value, but unless characters used in hash values don't comprise all possible characters from the document being processed, wouldn't the longest hash value needed to be unique be the same length as the original document? Or is there some kind of natural inefficiency in hash functions that causes them to not use all possible combinations of characters in the output string? My understanding is probably just incomplete at some point, but it seems odd to me that hash values are longer than the length of the doc – Goel Nimi Jan 3 '19 at 1:52
2

A hash generator is nothing but a function f which maps some integer domain X (the possible file contents, interpreted as integer numbers) to some integer codomain Y (the possible codes or tags, also interpreted as integer numbers). And if Y contains only numbers of given length (as you wrote in your question), but X contains arbitrary length files, then X has a bigger cardinality than Y, which means f cannot be injective, which means it cannot be reversible.

Adding the concept of additional "hash values for simple variations of the file" is just a modification of the function f, creating a new function g which maps X to the new codomain Y x Y x ... x Y (the cartesian product), where the number of factors is the number of "variations" involved. But if Y contains only numbers of given length, Y x Y x ... x Y is also a finite integer set with a smaller cardinality than X.

Note also if you would losen the constraint on Y and allow "arbitrary length hash codes", this does not automatically guarantee any hash function to be injective. Adding the idea of "variations" won't change this.

Opposed to this, if f is a lossless compression function (which means it is injective), Y needs to have at least the same cardinality as X. Larger files (=larger numbers) in X will typically be mapped to larger values in Y. A good compression function will map many numbers in X which have a lot "redundancy" in them (like repeating sequences) to smaller numbers in Y. But the pigeonhole principle dictates that there will also be numbers in X which are necessarily mapped to larger numbers.

Note that there are indeed injective, reversible functions f which are not used for compression, and not for hashing (to a fixed length code), but for mapping a domain X of integer values to some codomain Y of same size. These functions obfuscate the original input in a way one can only reconstruct the original value by brute-force trial-and-error. This is the idea behind cryptographic functions.

2
  • Would you mind clarifying for me the role cartesian sets play in this, as well as defining cardinality? Thank you for taking time to help me out, you gave me a great starting point for researching aspects of programming related to this. – Goel Nimi Dec 31 '18 at 18:11
  • @GoelNimi: Cardinality. And concerning cartesian sets: if you map a file x to a hash value f(x)=y1, and then a modification of the file m(x) to a hash value f(m(x))=y2, the result is a pair of two numbers (y1,y2), which is an element of Y x Y. – Doc Brown Jan 1 '19 at 1:38

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.