5 ms·

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 menti

by 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.

5 ms·

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 menti

by scj 10y ago

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.