What is the differences between data compression as used in e.g. the ZIP protocol and compression as performed in cryptographic hashes? Are there common properties as well, apart from creating a smaller representation of the data?

  • 2
    $\begingroup$ As usual, trying to create a go-to Q/A so we don't have to explain it over and over again :) $\endgroup$
    – Maarten Bodewes
    May 17, 2020 at 20:39

2 Answers 2

  • In data lossless compression we want the data recoverable from the compressed form. This is usually helpful if the entropy is low like text files, so-called zipping.

  • In data lossy compression like JPEG, we still want to get the image (data) but we don't care about the full quality of the image. This can be considered as the original data can be recovered approximately.

  • The compression function of hash functions (one-way compression function) takes two inputs and produces one output - the compression ratio doesn't need to be 2:1. The transformation is required to be

    • one way: i.e. given an output finding the input value should be difficult.
    • and, have avalanche property: each output bit must depend on all input bits.

Being one way is not a desired property for lossless compression, however, lossy compression is not totally one way but some information is lost. JPEG or similar compression is not a good compression for hash functions.

Avalance property doesn't suit the data compression since that causes a random behavior on the compression. In avalanche property, we want each output bit to have a 50% chance of flip for a bit flip of an input bit.

In short, a single word "compression" should not be used to identify those. Use the "data lossless compression" or "data lossy compression" for data compression and "compression function" for hash functions.

  • 2
    $\begingroup$ Some data compression algorithms have a fair degree of avalanche property, e.g. when they use arithmetic coding. However that's accidental, not by design. $\endgroup$
    – fgrieu
    May 18, 2020 at 6:26
  • $\begingroup$ I would not approve using the term "compression" at all when referring to irreversible functions. Lossy compression is appropriate because they are mostly, approximately reversible; but it's arguably more clear to teach (and think) of "compression" and "hashing" as separate, distinct, non-overlapping concepts and discourage referring to one-way hashing as compression because its properties are so substantially different; and talk about compression only when you have a pair of functions that can not only compress but also decompress. $\endgroup$
    – Peteris
    May 18, 2020 at 9:05
  • $\begingroup$ @fgrieu could you name one? $\endgroup$
    – kelalaka
    May 18, 2020 at 9:09
  • 2
    $\begingroup$ @kelalaka: my remark is based on tests two decades ago, with a Lempel-Ziv + arithmetic encoder, which IIRC was LZARI. I have not idea if this will exhibit the same effect. The diffusion is forward-only. $\endgroup$
    – fgrieu
    May 18, 2020 at 9:48
  • 1
    $\begingroup$ Isn't it useful to point out that hash functions are a one way avalanche to a set size for all input sizes? $\endgroup$
    – Hogan
    May 18, 2020 at 14:20

Think of crypto compression as information destruction. This relies on the output domain being smaller than the input domain via wacky cryptographic primitives. Thru a lot of $\oplus$ and $\boxplus$ operators.

Information is irretrievably lost and thus absolutely mathematically irreplaceable. So a one way function and thus secure (or not if the implementation is flawed, or susceptible to computational power).

The objectives of cryptography are not those of information preservation.


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.