In what follows, let Enc, Dec, Gen denote encryption, decryption and key generation, re$-$

spectively. If not otherwise stated, $M,C,K$ will be the message space, ciphertext space, and

space of keys, respectively. Probability distributions will usually be written in calligraphic

font, e$.$g$.,x,$ and the notation xlarrx will denote sampling $x$ according to the distribution

$x.$ For a finite set $x,$xlarrx denotes that $x$ is sampled from the uniform distribution on $x.$

Consider the probability space on $MC$ resulting from the following experiment, where

$M$ is an arbitrary distribution on the message space: sample mlarrM and klarr Gen and

output the pair $(m,c)$ where $c=En{c}_k(m).$ Denote by $C$ the marginal distribution on $C$

$($this is what you get if you perform the above experiment and just keep $c).$ Argue that

if the encryption scheme is perfectly secure$,$ then $C$ will not depend on $M.$ Then prove

or give a counterexample for the following statement: All ciphertexts in a perfectly

secure scheme are equally likely. That is$,$ for any $c_0,c_1$inC,

$P{r}_{\text{c}\text{l}\text{a}\text{r}\text{r}\text{C}}[c=c_0]=P{r}_{\text{c}\text{l}\text{a}\text{r}\text{r}\text{C}}[c=c_1].$