Perfect Secrecy and Message distribution I have been trying to come up with a proof of the following statement,
Suppose a cryptosystem achieves perfect secrecy for a particular plaintext probability
distribution then Prove that perfect secrecy is maintained for &quot;any&quot; plaintext probability distribution.
Well I know that the perfect secrecy scheme is independent of plaintext distribution, but how to prove the above statement? Any help would be appreciated.
I don't think the statement is true, and I will come to a counterexample later.
Formalization
One possible formalization of the statement could look like this:
Let $\mathcal{M}$ be the message space, and $\mathcal{C}$ the ciphertext space.
We define two arbitrary distributions over $\mathcal{M}$: $M_a$ and $M_b$,
where $\Pr_{m \in \mathcal{M}}[M_a = m] = p^\mathcal{M}_a(m)$ and $\Pr_{m \in \mathcal{M}}[M_b = m] = p^\mathcal{M}_b(m)$.
Additionally we need distributions over $\mathcal{C}$: $C_a$ and $C_b$ defined analogously.
An encryption scheme $\Pi = (\mathrm{Gen}, \mathrm{Enc}, \mathrm{Dec})$ is perfectly secret with respect to the distribution defined by $M_a$ if:
$\forall m\in\mathcal{M}, c\in\mathcal{C}. \Pr[M_a=m] = \Pr[M_a = m\ |\ C_a = c]$ and $\Pr[C_a = c] &gt; 0$, to avoid conditioning on an event with zero probability.
We want to show that given $\Pi$ fulfills the above definition, then it also fulfills the same definition with $M_a$ replaced by $M_b$.
Attempt to Prove
I first attempted (but did not succeed) at proving the statement.
My attempt looks like this:
First show that it suffices to show that the ciphertext distributions are equal
(i.e. that $\Pr[C_a = c] = \Pr[C_b = c]$ holds).
Then show that the ciphertext distributions are equal.
However, I was not able to prove these statements.
Refutation
I believe I have found a counterexample.
Lets first look at the definition of perfect secrecy:

There are two things I would like to point out:

the definition requires independence of the message from the ciphertext for any plaintext distribution, so your statement deviates from this requirement.
the equation only needs to hold for $\Pr[C = c] &gt; 0$

Counterexample
Let $\mathcal{M} = \mathcal{C} = \{0,1,2,3\}$.
Further, let our key-space be $\mathcal{K} = \{0,1\}$.
We define an encryption scheme that is perfectly secret for the messages $0$ and $1$, but not for $2$ and $3$:
\begin{equation*}
\mathrm{Enc}_k(m) = 
\begin{cases}
k \oplus m &amp; \text{if $m \in \{0,1\}$}\\
m &amp; \text{if $m \in \{2,3\}$}\\
\end{cases}
\end{equation*}
Additionally, we define a message distribution as follows:
\begin{equation*}
\Pr[\mathcal{M} = m] = 
\begin{cases}
\frac{1}{2} &amp; \text{for $m \in\{0,1\}$}\\
0 &amp; \text{for $m \in\{2,3\}$}\\
\end{cases}
\end{equation*}
We now show, that (1) $\Pi$ is perfectly secret with respect to our message distribution.
Then (2) we show that it is not perfectly secret for all message distributions.
1.
We need to show that
$\Pr[M = m] = \Pr[M = m\ |\ C = c]$.
We don't need to show this for $c \in \{2,3\}$ since for our message distribution, $\Pr[C = 2] = \Pr[C = 3] = 0$.
For $c \in \{0, 1\}: \Pr[M = m\ |\ C = c] = \frac{1}{2} = \Pr[M = m]$.
Therefore, the encryption scheme is perfectly secret for the given message distribution.
2.
However, given a message distribution that assigns $2$ or $3$ a non-zero probability, the scheme is trivially not perfectly secret:
$\Pr[M = 2] \neq 0 = \Pr[M = 2\ |\ C = 3]$
Therefore the scheme is not perfectly secret for all message distributions, and thus the statement does not hold in general.
Appendix
For completeness here is the decryption algorithm:
\begin{equation*}
\mathrm{Dec}_k(c) =
\begin{cases}
c \oplus k &amp; \text{if $c \in \{0,1\}$}\\
c &amp; \text{if $c \in \{2,3\}$}
\end{cases}
\end{equation*}
and the key generation:
\begin{equation*}
\mathrm{Gen}() = k \stackrel{sample}{\leftarrow}\{0,1\}
\end{equation*}