1
$\begingroup$

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.

Improve this question
$\endgroup$
9
  • 1
    $\begingroup$ What have you tried so far? Which definition are you using for perfect secrecy? $\endgroup$
    – ambiso
    Nov 30, 2020 at 9:56
  • $\begingroup$ 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}$$ $\endgroup$
    – SSA
    Nov 30, 2020 at 11:01
  • $\begingroup$ 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. $\endgroup$
    – SSA
    Nov 30, 2020 at 11:27
  • $\begingroup$ I tried to use this definition of perfect secrecy: pr(x)=pr(x|y), where $x\in M$ and $y\in C$ @cisnjxqu $\endgroup$
    – Vshi
    Nov 30, 2020 at 11:37
  • $\begingroup$ Have you tried formalizing the statement you want to prove? $\endgroup$
    – ambiso
    Nov 30, 2020 at 12:20

2 Answers 2

Reset to default
3
$\begingroup$

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:

Definition of Perfect Secrecy (from Introduction to Modern Cryptography by Katz and Lindell

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*}

Improve this answer
$\endgroup$
8
  • $\begingroup$ 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. $\endgroup$
    – kelalaka
    Dec 1, 2020 at 19:51
  • $\begingroup$ 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| $\endgroup$
    – SSA
    Dec 2, 2020 at 7:59
  • $\begingroup$ @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. $\endgroup$
    – ambiso
    Dec 2, 2020 at 8:02
  • $\begingroup$ @SSA Yes, the key is chosen uniformly random $\endgroup$
    – ambiso
    Dec 2, 2020 at 8:08
  • $\begingroup$ 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? $\endgroup$
    – SSA
    Dec 2, 2020 at 11:06
0
$\begingroup$

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) }$$

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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}$ $\endgroup$
    – Vshi
    Dec 21, 2020 at 12:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.