153 reputation
3
bio website
location
age
visits member for 1 year, 10 months
seen Jun 18 '12 at 20:05

Jun
15
comment Why is ciphertext from low entropy plaintext not compressible?
Perhaps I'm meandering a bit from the point, but AES relies on empirical evidence of it's security, right? So, the question I'm dying to know is: Is H(my_aes_ciphertext) (a) definitely less than len(my_aes_ciphertext) (b) approximately the same as len(my_aes_ciphertext), or (c) we're predicating the security of AES in part that H(my_aes_ciphertext) is uncomputable, even though (a) may be true? Thanks again, hope I'm not making too much of a clown out of myself.
Jun
15
comment Why is ciphertext from low entropy plaintext not compressible?
Well, thanks for the welcome!
Jun
15
comment Why is ciphertext from low entropy plaintext not compressible?
Thanks for the response. So, in principle, is the kolmogorov complexity of the ciphertext above approximately equal to the sum of the parts that generate it? In other words, is the apparent incompressability of the ciphertext just an artifact of the compression heuristics, and doesn't imply that it isn't indeed incompressible? Can a compression algorithm be crafted to exploit the fact that AES generated the ciphertext?