2
$\begingroup$

I've read the definition of perfect secrecy as the following:

A cryptosystem has perfect secrecy if $\Pr(x | y) = \Pr(x)$, for all $x \in P$ and $y \in C$, where $P,C$ are respectively the set of plaintexts and ciphertexts.

Now suppose there are 26 keys in the Shift Cipher (SC) with probability 1/26. Then for any plaintext with probability distribution, SC has perfect secrecy.

The proof starts with:

$$\Pr(y) = \sum_{k \in \mathbb{Z}_{26}} \Pr(k)\Pr\left(x = d_k(y)\right)$$

I didn't comprehend this part (the probability distr. on $C$), and the way it's calculated.

obs.: the encryption rule for shift cipher is $e_k(x) = (x+k) \text{ mod 26} (x \in \mathbb{Z_{26}})$.

Also note that $K$ is the set of keys.

$\endgroup$
9
  • $\begingroup$ Any $c = x + k$, so probability of selecting $k$ times probability of there is $x$ decryption of $y$ under the key. In this case, second is always 1. And sum all. $\endgroup$
    – kelalaka
    Dec 26, 2021 at 17:22
  • $\begingroup$ Why second is always 1? $\endgroup$ Dec 26, 2021 at 17:29
  • $\begingroup$ For every plaintext there is always a ciphertext under any key, and the reverse is also true. $\endgroup$
    – kelalaka
    Dec 26, 2021 at 17:30
  • 1
    $\begingroup$ When ready, you can write your own answer, this way you can learn more. Our community will check your asnwer... $\endgroup$
    – kelalaka
    Dec 26, 2021 at 17:34
  • 1
    $\begingroup$ If you read the answer properly you need to see that; Shift Cipher (SC) can only attain perfect secrecy if it is restricted to one letter encryption. So one needs to mention this; let $SC'$ be the modified $SC$ such that for a random key it only encrypts one character. In the end, this is what One-Time-Pad if you continue to use another random key per character. $\endgroup$
    – kelalaka
    Dec 27, 2021 at 11:39

1 Answer 1

2
$\begingroup$

We will prove that $\Pr[x |y] = \Pr[x]$, first notice that, since, for each element of $P$, we always have an element of $C$, under a key, $\Pr\left(x = d_k(y)\right) = 1$, so:

$$\Pr(y) = \sum_{k \in \mathbb{Z}_{26}} \Pr(k)\Pr\left(x = d_k(y)\right) = \sum_{k \in \mathbb{Z}_{26}} \Pr(k) $$

Now, the sum stands for the union of all associations of one key and a decryption.

But, since $e_k(x) = (x+ K) = y \mod 26$, we conclude that $\Pr\left(x = d_k(y)\right) = \Pr (y-K) = 1$. It's clear that $\Pr(k) = 1/26$, so $\Pr(y) = 1/26$.

Now, $\Pr[y|x] = \Pr[K] = 1/26$, because given $x$, $y$ is unique (uniquely determined via the $K$). Now by Bayes' Theorem we know:

$$\Pr[x|y] = \frac{\Pr[x]\Pr[y|x]}{\Pr[y]} = \frac{\Pr[x]\cdot 1/26}{1/26} = \Pr[x]$$

and this concludes the fact that Shift Cipher brings Perfect Secrecy.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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