Prove that the affine cipher over Z26 has perfect secrecy if every key is used with equal probability of 1/312

Question

Prove that the affine cipher over Z26 has perfect secrecy if every key is used with equal probability of 1/312.

Just some guidance/help with this problem would be greatly appreciated not sure how to start the proof. Many thanks!

Answer 1

This would usually I think be more suited as a comment, but you were looking for guidance instead of a complete answer as it were, and I don't have enough reputation to comment.

I'd highly recommend Claude Shannon's introduction (the literal introduction, he developed the concept) to the question you pose. Here’s the paper (PDF) and the section is Part 10 on Pg. 679. The more broad statement of your question is Theorem 6, but he does (as he always does) an incredibly good job of approaching both the motivation for the theorem as well as the proof, the latter of which he gives in relatively informal way.

Answer 2

Let's remember first what an Affine cipher is:

Let $P = C = \mathbb{Z_{26}}$ and let

$$K = \{(a,b) \in \mathbb{Z_{26} \times}\mathbb{Z_{26} : gcd(a,26) = 1 }\}$$

For $K = (a,b) \in K$, define

$$e_k(x) = (ax+b) \mod 26$$

and $d_k(y) = a^{-1} (y- b) \mod 26$ for $x,y \in \mathbb{Z_{26}}$.

Now, let's go to the solution:

There are 312 keys, due due $12 \times 26 = 312$, this is, 12 because there are twenlve coprimes with 26 mod 26, and $b$ can be any number in $\mathbb{Z_{26}}$. Now, let us pick one key and one encryption, getting one cyphertext, summing over all possibilities, we get:

$$\Pr[y] = \sum_{k \in K} \Pr[k] \Pr[d_k(y)] = 12/312\Pr[a] + ... + 12/312 \Pr[z] $$

$$ = 1/26 \cdot(\Pr[a] +...+\Pr[z]) = 1/26$$

By Bayes' Theorem, we have:

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

Obs.: there are 12 keys that encrypt $x$ to $y$, that's why we have 12/312, note also that for each $a$, the key $(a, y-ax)$ encrypts $x$ to $y$.