The trouble with compression. Let $($E$,$ D$)$ be a semantically secure cipher that operates on messages in $\{0,1\}<=$n $($i$.$e$.$ messages whose length is at most n bits$).$ Suppose that the ciphertext output by the encryption algorithm is exactly $128$ bits longer than the input plaintext. To reduce ciphertext size, there is a strong desire to combine encryption with lossless compression. We can think of compression as a function from $\{0,1\}<=$n to $\{0,1\}<=$n where, for some messages, the output is shorter than the input. As always, the compression algorithm is publicly known to everyone. a$.$ Compress$-$then$-$encrypt: Suppose the encryptor compresses the plaintext message m before passing it to the encryption algorithm E$.$ Some n$-$bit messages compress well, while other messages do not compress at all. Show that the resulting system is not semantically secure by exhibiting a semantic security adversary that obtains advantage close to $1.$ b$.$ Encrypt$-$then$-$compress: Suppose that instead, the encryptor applies compression to the output of algorithm E $($here you may assume the compression algorithm takes messages of length up to n $+128$ bits as input$).$ Explain why this proposal is of no use for reducing ciphertext size.