# 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 "any" 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.

• What have you tried so far? Which definition are you using for perfect secrecy? – cisnjxqu Nov 30 '20 at 9:56
• Shannon Theorem :if |K| = |C| = |P| then the system provides perfect secrecy iff (1) every key is used with equal probabilify 1/|K|, and (2) for every x ${\in}$ P and y ${\in}$ C, there exists a unique key k${ \in}$ K such that $${e_k(x)=y}$$ – SSA Nov 30 '20 at 11:01
• so given a ciphertext, an attacker can no find the plaintext. Pr[p/c]= Pr[p], i.e given a ciphertext probability of a plaintext is same as probability of a plaintext alone. Which is attack can't learn anything from ciphertext about a plaintext. so, if one particular plaintext has perfect secrecy (in thoery) then 'any' plaintext has perfect secrecy. – SSA Nov 30 '20 at 11:27
• I tried to use this definition of perfect secrecy: pr(x)=pr(x|y), where $x\in M$ and $y\in C$ @cisnjxqu – Vshi Nov 30 '20 at 11:37
• Have you tried formalizing the statement you want to prove? – cisnjxqu Nov 30 '20 at 12:20

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] > 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:

1. the definition requires independence of the message from the ciphertext for any plaintext distribution, so your statement deviates from this requirement.
2. the equation only needs to hold for $$\Pr[C = c] > 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 & \text{if m \in \{0,1\}}\\ m & \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} & \text{for m \in\{0,1\}}\\ 0 & \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 & \text{if c \in \{0,1\}}\\ c & \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*}$$

• what is the value of $k \oplus m$? Is it 0 or 1? Then your keyspace is already short than the message space, if not it may already be insecure. – kelalaka Dec 1 '20 at 19:51
• Lemma 1: An encryption scheme (Gen, Enc, Dec) over a message space M is perfectly secret if and only if for every probability distribution over M, every ${m_0, m_1 \in M}$, and every ciphertext ${c \in C}$ $${Pr[C=c|M=m_0]}=Pr[C=c|M=m_1]$$ By Lemma 1:for any ${m_i,m_j \in M}$ $${Pr[K=k_i]=Pr[Enc_k(m_i)=c]=Pr[Enc_k(m_j)=c]=Pr[K=k_j]}$$ Since ${k_i \neq k_j for i \neq j}$, this mean each key is chosen with probability 1/|K| – SSA Dec 2 '20 at 7:59
• @kelalaka yes $k \oplus m \in \{0,1\}$. Yes this encryption scheme is not perfectly secret with respect to all message distributions, but it is perfectly secret with regards to message distributions that only assign $0$ and $1$ a non-zero probability. – cisnjxqu Dec 2 '20 at 8:02
• @SSA Yes, the key is chosen uniformly random – cisnjxqu Dec 2 '20 at 8:08
• But original statement is " Suppose a cryptosystem achieves perfect secrecy for a particular plaintext probability distribution p0. Prove that perfect secrecy is maintained for any plaintext probability distribution." and it is true. because if perfect secrecy is proved for any message ${m_i}$ then probability of any ciphertext ${c \in C}$ equally possible for any message ${m \in M}$ because of random probability of a chosen key i.e. ${\frac{1}{|K|}}$. why do you think it is not correct? – SSA Dec 2 '20 at 11:06

Proof: $${Pr[Y=y]= \sum_{K \in Z_{26}} Pr[K=k] Pr[x=d_k(y)] }$$ $$=\frac{1}{26}{\sum_{K \in Z_{26}} Pr[x=y-K]}$$ $$={\frac{1}{26}}$$ Hence, $${Pr [y|x] = Pr[K=(y-x) mod 26] }$$ $$={\frac{1}{26}}$$

Above equation shows that For every pair of yand x there is exactly one key, and probability of that key is 1/26. i.e., $${Pr (x|y) = Pr(x) }$$

• You have assumed here $|M|=|K|$, what if $|K|\ge |M|$? \\ How can we say that if $|K|\ge |M|$ we will still have $Pr[K=k]=\frac{1}{K}$ – Vshi Dec 21 '20 at 12:03