Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

M: plaintext space with a probability distribution $P_1$

K: keys space with a probability distribution $P$

probabilities on spaces M and K are independent.

C: cipher text space with an induced probability distribution from spaces M and K as follows:

$enc_k:M\rightarrow C$ and $dec_k: C\rightarrow M$ such that $dec_k(enc_k(x))=x$.

$C(k)=\left\{enc_k(x)|x\in M\right\}$

and $P[C=y]=\sum_{k,y\in C(k)} P[K=k] P[M=dec_k(y)]$

Moreover, $P[C=y|M=x]=\sum_{k,x=dec_k(y)} P[K=k]$.

A Cryptosystem has perfect secrecy if $P[M=x|C=y]=P[M=x]$.

My question is:

Suppose I have a cryptosystem that has perfect secrecy for a given probability distribution $P_1$ on the plaintexts space M. That is $P[M=x|C=y]=P_1[M=x]$

Will it have perfect secrecy for another probability distribution $P_2$ on M?

Is there a proof?

share|cite|improve this question
up vote 2 down vote accepted

Since the question makes an awful mess of sample spaces and random variables, it seems necessary to first reformulate the model.

One considers random variables $M$ and $K$ defined on a given probability space, with values in some given sets $\mathcal M$ and $\mathcal K$ respectively, and a function $e:\mathcal K\times\mathcal M\to\mathcal C$ with values in another given set $\mathcal C$. The hypotheses are that:

$\quad$ 1. The random variables $M$ and $K$ are independent.

$\quad$ 2. For every $k$ in $\mathcal K$, the function $e(k,\ )$ is one-to-one.

Any triple $(M,K,e)$ such that 1.-2. hold is called a cryptosystem. A cryptosystem $(M,K,e)$ has perfect secrecy if additionally:

$\quad$ 3. The random variables $M$ and $C=e(K,M)$ are independent.

Then the formulas in the post are merely Bayes decompositions, for example, for any cryptosystem $(M,K,e)$, the independence of $M$ and $K$ yields, for every $c$ in $\mathcal C$, $$ \mathbb P(C=c)=\sum_{k\in\mathcal K}\mathbb P(K=k)\cdot\mathbb P(e(k,M)=c), $$ and, for every $c$ in $\mathcal C$ and $m$ in $\mathcal M$, $$ \mathbb P(C=c\mid M=m)=\mathbb P(e(K,m)=c)=\sum_{k\in\mathcal K}\mathbb P(K=k)\cdot\mathbf 1_{e(k,m)=c}. $$ The question is whether a cryptosystem $(M_1,K,e)$ having perfect secrecy implies that any other cryptosystem $(M_2,K,e)$ based on the same random variable $K$ and the same deterministic function $e$, still has perfect secrecy. In other words:

Assume that $(M_1,K)$ is independent, that $(M_1,e(K,M_1))$ is independent, that $(M_2,K)$ is independent, and that each $e(k,\ )$ is one-to-one. Does all this imply that $(M_2,e(K,M_2))$ is still independent?

This needs not be the case. For a toy counterexample, assume that $M_1$ and $K$ are uniform on $\{\pm1\}$, $M_2$ is uniform on $\{\pm1,\pm2\}$, $(M_1,K,M_2)$ are independent, and $e:(k,m)\mapsto km$. Then $(M_1,e(K,M_1))$ is independent but $(M_2,e(K,M_2))$ is not.

share|cite|improve this answer
I have indeed made an awful mess, you’re right. I’m not sure I’m following you all the way. Can you explain a bit more your counter example? What do you mean when you say uniform distribution on $\left\{\pm 1\right\}$ and $\left\{\pm 1 ,\pm 2\right\}$ ? – epsilon Dec 19 '12 at 14:22
The uniform distribution $u$ on a set $S$ of sise $s$ puts mass $1/s$ on each element of $S$, hence, for every $T\subset S$, the measure $u(T)$ is the size of $T$ divided by the size of $S$. – Did Dec 19 '12 at 14:42
Yes but since both $M_1,M_2$ are probability distributions on the same space $\mathcal{M}$. Is that possible? Supposing $\mathcal{M}=\left\{a,b\right\}$ you'll define $M_1(a)=M_1(b)=\frac{1}{2}$ and then $M_2(a)=M_2(b)=\frac{1}{4}$? Then $M_2$ will not be a probability distribution on $\mathcal{M}$. – epsilon Dec 19 '12 at 14:55
I will certainly define nothing of the sort (what a strange idea). In the example, both $M_1$ and $M_2$ are probability distributions on $\{-2,-1,1,2\}$. It is true that $M_1$ puts mass zero on $\pm2$ but I see no reason to suspect the result you suggest might hold, even if one compares probability measures with the same support (a hypothesis you did not mention in the post). By the way, what made you think the result might hold? – Did Dec 19 '12 at 15:24
You’re right. It is clear now to me both define probability distributions on $\left\{-2,-1,1,2\right\}$. I was asked to prove that if a cryptosystem has perfect secrecy for a given distribution on $\mathcal{M}$ it will have perfect secrecy for all other possible distributions. It sounded a bit strange to be honest as I came upon definitions as the following : A cipher provides perfect secrecy if and only if for any probability distribution from which the plaintext is drawn, and for any plaintext-ciphertext pair $(M_0,C_0)$, we have $Pr[PT = M_0 | CT = C_0] = Pr[PT = M_0]$. – epsilon Dec 19 '12 at 15:53

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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