Score:0

Perfect Secrecy for Shift Cipher

au flag

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.

kelalaka avatar
in flag
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.
João Víctor Melo avatar
au flag
Why second is always 1?
kelalaka avatar
in flag
For every plaintext there is always a ciphertext under any key, and the reverse is also true.
João Víctor Melo avatar
au flag
Now, I can comprehend.
kelalaka avatar
in flag
When ready, you can write your own answer, this way you can learn more. Our community will check your asnwer...
kelalaka avatar
in flag
Are you sure that this SC has the original SC or a modified one that only accepts one character to encrypt? [Can a shift cipher attain perfect secrecy?](https://crypto.stackexchange.com/q/5662/18298)
João Víctor Melo avatar
au flag
I don't comprehend well what you mean.
kelalaka avatar
in flag
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.
kelalaka avatar
in flag
Did you notice the point?
Score:0
au flag

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.

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.