### Perfect Secrecy

A cryptosystem has perfect secrecy if for any message `x` and any encipherment `y`, `p(x|y)=p(x)`.

This implies that there must be for any message, cipher pair at least one key that connects them. Hence:

```    |K| >= |C| >= |P|
```
In the boundary case of equality we have the following theorem:

Theorem(Shannon perfect secrecy)
Suppose a cryptosystem with `|K|=|C|=|P|`. The cryptosystem has perfect secrecy if and only if

• each key is used with equal probability `1/|K|`,
• for every plaintext `x` and ciphertext `y` there is a unique key `k` such that `e_k(x)=y`.

Proof
Suppose perfect secrecy, i.e. `p(x|y)=p(x)` for all `x` and `y`. Unless `p(x)=0`, there must be enough keys so that any ciphertext can be decoded as a given plaintext, that is, `|K|>=|C|`, but by supposition, equality must hold. Hence there is a unique key for every `x` `y` pair.

Suppose keys `k_1, k_2, ... ` are the unique keys such that `d_k_i(y)=x_i`. Using Bayes law:

```    p(x_i|y) = ( p(y|x_i) p(x_i) ) / p(y)
```
Using the assumption of perfect secrecy, we have:
```   p(y|x_i) = p(y)
```
hence each `k_i` must occur with the same probability

We now assume that `p(k)=1/|K|` and that there is a unique key relating any plaintext-ciphertext pair.

```    p(x|y) = ( p(y|x) p(x) ) / p(y)
```
By the uniqueness of keys, `p(y|x)=1/|K|`. We also calculate
```   p(y) = sum_k p(k) p(d_k(y))
= 1/|K| sum_k p(d_k(y))
= 1/|K| sum_x p(x)
= 1/|K|
```
Cancelling the `1/|K|` gives the result `p(x|y) = p(x)`, that is, perfect secrecy.