2
$\begingroup$

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?

1 Answers 1

3

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.

  • 0
    Sorry couldn’t fit that in one comment. I though I was missing an equivalence between different definitions. As it seems I’m not. Thank you for your time and effort.2012-12-19