1

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!

Leafar
  • 1,723
  • Why do you believe that this is the case? – joriki Feb 27 '20 at 04:00
  • Because here we are encrypting twice using the same cryptosystem, and it seems that we gain no advantage doing that. – Leafar Feb 27 '20 at 08:20
  • Maybe condition on the intermediate value? Note also that $S$ perf.sec. does not imply $S \circ S$ perf.sec. – Henno Brandsma Feb 29 '20 at 11:34
  • I am sure that if $S$ has perfect secrecy then $S \circ S$ has perfect secrecy. Because plaintexts and keys are supposed to be independent (this is for all cryptosystems) and in $S \circ S$ keys $k$ and $k'$ are chosen independently. – Leafar Mar 01 '20 at 05:59

0 Answers0