Prove that if $S \circ S$ has perfect secrecy, then $S$ has perfect secrecy

65 Views Asked by At

Consider a cryptosystem $S=(X,X,K,e,d)$. In this case, the set of ciphertexts is the same as the set of plaintexts, so we can make the following definition:

We define the cryptosystem $S \circ S = (X,X,K \times K, e',d')$, which is the composition cryptosystem of $S$ with itself, where \begin{align*} e'_{(k,k')}(x) = e_{k'}(e_k(x)) \quad \text{and} \quad d'_{(k,k')}(z) = d_{k}(d_{k'}(z)). \end{align*}

We suppose that $S \circ S$ has perfect secrecy, that is $$P(X=x | Z=z) = P(X=x)$$ for all $x \in X$ and $y \in Y$, where $Z$ is the random variable associated with ciphertexts from $X$, and $X$ is the random variable associated with plaintexts from $X$.

I want to prove that $S$ has perfect secrecy, that is, $$P(X=x | Y=y) = P(X=x)$$ for all $x \in X$ and $y \in Y$.

I tried to introduce the variable $Z$: $$P(X=x | Y=y) = \sum_z P(X=x \wedge Z=z | Y=y)$$ but I cannot derive the result that I want.

Thanks in advance!