4 ms·

You can't compress after encryption. Encrypted content should be indistinguishable from random data. So encrypt than compress shouldn't be able to yield any r

You can't compress after encryption. Encrypted content should be indistinguishable from random data. So encrypt than compress shouldn't be able to yield any reasonable compression.

deleted 10y ago
[deleted]
choosername 10y ago
wit truly random data, patterns should randomly appear.
- gameofdrones 10y ago
  https://en.wikipedia.org/wiki/Entropy_(information_theory) https://en.wikipedia.org/wiki/Entropy_(information_theory)
  - choosername 10y ago
    I'm sorry, that article is far too long to tell me what you are trying to say. All I can gather is, I was wrong
    - LeoPanthera 10y ago
      tl;dr Random data may appear to have patterns, but those patterns do not repeat, so they cannot be compressed.
      - angry_octet 10y ago
        Ah, but they can repeat! There is a finite chance that any sequence of any length will occur in a random sequence. So while a compression alg applied to a very large amount of random data is unlikely to reduce the size, it is quite possible to achieve some compression on smaller blocks.
        taneq 10y ago
        Any given _example_ of a random sequence may have less than maximum entropy, and so may be compressible, but a truly random sequence _in general_ will not be compressible. So you can make a compression algorithm that will compress random data in some cases but it will never be able to compress any arbitrary random data. Does this help?
        analogj 10y ago
        You should take a look at the almost 15 year old (and unsolved) "Random Compression Challenge" http://marknelson.us/2012/10/09/the-random-compression-challenge-turns-ten/ http://marknelson.us/2012/10/09/the-random-compression-chall...
    - gameofdrones 10y ago
      That is still your problem and you need to take responsibility for it. It is wiser to learn and know what you're talking about, don't just add ambient, useless, incorrect noise.
      - Retra 10y ago
        Saying something true but burying it is not wise either.
- jahewson 10y ago
  Encrypted data is "indistinguishable from random data" but it is not actually random data. No patterns will appear.
  - qu4z-2 10y ago
    If patterns appear in random data, and no patterns appear in encrypted data, then it's trivially distinguishable from random data: look for patterns.
    - qu4z-2 10y ago
      To be clear, I'm not claiming that encrypted data is compressible. I'm just pointing out that any detectable "patterns" that appear in random data but not encrypted data are inconsistent with the claim that random and encrypted data are indistinguishable. Also if you find such a "pattern" that's probably a good starting point for breaking whatever cipher you're using.
- zzazzdsa 10y ago
  There's a pretty easy proof to show why compression of truly random data is impossible. Let C be a compression algorithm. Assume that for all bit strings S, C(S) is not longer than S, and assume that there exists strings S' such that C(S') is shorter than S'. Also, assume that for any two distinct bit strings S1 and S2, C(S1) != C(S2). Let S'' be the shortest such string: the shortest string that C shortens. Let the length of S'' be M, and the length of C(S'') be N < M. Note N >= 1, and by assumption every string of length N does not have its length changed by C. There are 2^N strings of length N, and by assumption it is easy to see that since the images of any pair of N bit strings under C are distinct, every string of N bits is the image of some other N bit string. But now, S'' has length M but has an image of length N. This necessarily collides with the image of some string of length N, a contradiction. Thus, for any compression algorithm which is injective (in effect, reversible) and successfully shortens some strings, the algorithm must lengthen some others. What this short proof shows is that even though random data may have patterns, no compression algorithm can successfully leverage this for every random string.
scj 10y ago
Let's say you are using a one-time pad, and the encrypted text is a string of a million A characters. While unlikely to the point that it is barely worth mentioning, it is possible. And could trivially be compressed. I think your main point is correct, just presented too strongly. In many cases compression after encryption will yield poor results. But I wouldn't go so far as to say that it can't be done.
- pshc 10y ago
  This seems overly pedantic. In my mind "incompressible" does not mean "there are absolutely zero situations in which the output could be shorter than the input." There will always be (compression scheme, input) combinations that produce smaller outputs. The qualifying criteria is "does expected input data typically compress?" For a reasonable definition of incompressible, properly encrypted data is it.
  - deleted 10y ago
    [deleted]
- bryondowd 10y ago
  My intuition says that if your ciphertext after using a one-time pad is trivially compressible, it means there's a strong correlation between your plaintext and your key. It's an interesting thought. Consider using basic modular addition of letters, with A=1, B=2 ... Z = 26. If your plaintext is HELLO, and you get AAAAA as ciphertext, then your key has to be SVOOL. If you look, that's just an inversion of each letter. H is the 8th letter of the alphabet, whereas S is the 8th from the end, etc. So, your one-time pad was incidentally a simple translation of your message. I'm not sure if there's any interesting information being leaked this way. Perhaps by seeing that the encrypted message can be heavily compressed, or knowing that it has been heavily compressed, you can assume that the encryption key has some very improbable patterns, and use that to bound guesses about the encryption key. Not an expert. Not even an intermediate.

You can't compress after encryption. Encrypted content should be indistinguishable from random data. So encrypt than compress shouldn't be able to yield any reasonable compression.

deleted 10y ago

[deleted]

choosername 10y ago

wit truly random data, patterns should randomly appear.

gameofdrones 10y ago
https://en.wikipedia.org/wiki/Entropy_(information_theory) https://en.wikipedia.org/wiki/Entropy_(information_theory)
- choosername 10y ago
  I'm sorry, that article is far too long to tell me what you are trying to say. All I can gather is, I was wrong
  - LeoPanthera 10y ago
    tl;dr Random data may appear to have patterns, but those patterns do not repeat, so they cannot be compressed.
    - angry_octet 10y ago
      Ah, but they can repeat! There is a finite chance that any sequence of any length will occur in a random sequence. So while a compression alg applied to a very large amount of random data is unlikely to reduce the size, it is quite possible to achieve some compression on smaller blocks.
      - taneq 10y ago
        Any given _example_ of a random sequence may have less than maximum entropy, and so may be compressible, but a truly random sequence _in general_ will not be compressible. So you can make a compression algorithm that will compress random data in some cases but it will never be able to compress any arbitrary random data. Does this help?
      - analogj 10y ago
        You should take a look at the almost 15 year old (and unsolved) "Random Compression Challenge" http://marknelson.us/2012/10/09/the-random-compression-challenge-turns-ten/ http://marknelson.us/2012/10/09/the-random-compression-chall...
  - gameofdrones 10y ago
    That is still your problem and you need to take responsibility for it. It is wiser to learn and know what you're talking about, don't just add ambient, useless, incorrect noise.
    - Retra 10y ago
      Saying something true but burying it is not wise either.
jahewson 10y ago
Encrypted data is "indistinguishable from random data" but it is not actually random data. No patterns will appear.
- qu4z-2 10y ago
  If patterns appear in random data, and no patterns appear in encrypted data, then it's trivially distinguishable from random data: look for patterns.
  - qu4z-2 10y ago
    To be clear, I'm not claiming that encrypted data is compressible. I'm just pointing out that any detectable "patterns" that appear in random data but not encrypted data are inconsistent with the claim that random and encrypted data are indistinguishable. Also if you find such a "pattern" that's probably a good starting point for breaking whatever cipher you're using.
zzazzdsa 10y ago
There's a pretty easy proof to show why compression of truly random data is impossible. Let C be a compression algorithm. Assume that for all bit strings S, C(S) is not longer than S, and assume that there exists strings S' such that C(S') is shorter than S'. Also, assume that for any two distinct bit strings S1 and S2, C(S1) != C(S2). Let S'' be the shortest such string: the shortest string that C shortens. Let the length of S'' be M, and the length of C(S'') be N < M. Note N >= 1, and by assumption every string of length N does not have its length changed by C. There are 2^N strings of length N, and by assumption it is easy to see that since the images of any pair of N bit strings under C are distinct, every string of N bits is the image of some other N bit string. But now, S'' has length M but has an image of length N. This necessarily collides with the image of some string of length N, a contradiction. Thus, for any compression algorithm which is injective (in effect, reversible) and successfully shortens some strings, the algorithm must lengthen some others. What this short proof shows is that even though random data may have patterns, no compression algorithm can successfully leverage this for every random string.

scj 10y ago

Let's say you are using a one-time pad, and the encrypted text is a string of a million A characters. While unlikely to the point that it is barely worth mentioning, it is possible. And could trivially be compressed. I think your main point is correct, just presented too strongly. In many cases compression after encryption will yield poor results. But I wouldn't go so far as to say that it can't be done.

pshc 10y ago
This seems overly pedantic. In my mind "incompressible" does not mean "there are absolutely zero situations in which the output could be shorter than the input." There will always be (compression scheme, input) combinations that produce smaller outputs. The qualifying criteria is "does expected input data typically compress?" For a reasonable definition of incompressible, properly encrypted data is it.
- deleted 10y ago
  [deleted]
bryondowd 10y ago
My intuition says that if your ciphertext after using a one-time pad is trivially compressible, it means there's a strong correlation between your plaintext and your key. It's an interesting thought. Consider using basic modular addition of letters, with A=1, B=2 ... Z = 26. If your plaintext is HELLO, and you get AAAAA as ciphertext, then your key has to be SVOOL. If you look, that's just an inversion of each letter. H is the 8th letter of the alphabet, whereas S is the 8th from the end, etc. So, your one-time pad was incidentally a simple translation of your message. I'm not sure if there's any interesting information being leaked this way. Perhaps by seeing that the encrypted message can be heavily compressed, or knowing that it has been heavily compressed, you can assume that the encryption key has some very improbable patterns, and use that to bound guesses about the encryption key. Not an expert. Not even an intermediate.