### 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.