If $T' \circ T$ is perfectly secure, is then $T'$ or $T$ perfectly secure?

28 Views Asked by At

Let $T = (X, Y, K, e, d)$ and $T' = (Y, Z, K', e', d')$ be cryptosystems, and define $T' \circ T = (X, Z, K \times K', e'', d'')$ where $e''_{(k, k')}(x)=e'_{k'}(e_k(x))$ and $d''$ is defined similarly.

The point is to prove or find a counterexample to the following statement: if $T' \circ T$ is perfectly secure, i.e. $\text{Pr}(X=x\mid Z=z)=\text{Pr}(X=x)$, then $T$ or $T'$ is perfectly secure.

I believe that the statement is true, but I haven't managed to prove it on my own. Here's my attempt:

$$\begin{align}\text{Pr}(X=x) &= \text{Pr}(X=x\mid Z=z) \\ \Leftrightarrow \text{Pr}(X=x) &= \frac{\text{Pr}(X=x, Z=z)}{\text{Pr}(Z=z)} \\ \Leftrightarrow \text{Pr}(X=x) &= \frac{\sum_{y\in Y}\text{Pr}(X=x, Y=y, Z=z)}{\text{Pr}(Z=z)} \\ \Leftrightarrow \text{Pr}(X=x) &= \frac{\sum_{y\in Y}\text{Pr}(X=x \mid Y=y)\;\text{Pr}(Y=y \mid Z=z)\;\text{Pr}(Z=z)}{\text{Pr}(Z=z)} \\ \Leftrightarrow \text{Pr}(X=x) &= \sum_{y\in Y}\text{Pr}(X=x \mid Y=y)\;\text{Pr}(Y=y \mid Z=z) \end{align}$$

It seems like this expression can only be true if $\text{Pr}(X=x \mid Y=y) = \text{Pr}(X=x)$ or if $\text{Pr}(Y=y \mid Z=z) = \text{Pr}(Y=y)$, which is what we're trying to prove here. But this isn't really enough, is it?

1

There are 1 best solutions below

0
On BEST ANSWER

Perfect secrecy as stated is what we usually call as Shannon's secrecy. It is equivalent to The following categorization:

An encryption scheme satisfies perfect secrecy if for all messages $m_1, m_2$ in message space $M$ and all ciphertexts $c \in C$, we have $$\Pr_{k \leftarrow K}[Enc(K, m_1) =c] =\Pr_{k \leftarrow K}[Enc(K, m_2) =c].$$ where both probabilities are taken over the choice of $k \in K$ and over the coin tosses of the (possibly) probabilistic algorithm $Enc$.

From this, it can be shown that for perfect secrecy a cryptosystem must satisfy $|K| \geq |M|$.

Based on this, suppose $|X|=a, |K|=b$ and $|Y|=c, |K'|=d$, then for perfect secrecy of $T' \circ T$, we should have $bd \geq a$.

From this you want to check if this necessarily implies either $a \geq b$ or $c \geq d$. As you can see the conclusion is not guaranteed. Hence the statement is not true.