Cipher

A cipher is defined over the spaces of:

All Keys, $\mathscr{K}$

All Messages, $\mathscr{M}$

All Cipher texts, $\mathscr{C}$

Cipher (defined as a triple, $(\mathscr{K}, \mathscr{M}, \mathscr{C})$) as a pair of algorithms $(\mathbf{E}, \mathbf{D})$ where $\mathbf{E}$ represents the encryption algorithm and $\mathbf{D}$ represents the decryption algorithm.

$$\begin{equation} \mathbf{E}: \mathscr{K} \times \mathscr{M} \rightarrow \mathscr{C} \end{equation}$$

and

$$\begin{equation} \mathbf{D}: \mathscr{K} \times \mathscr{C} \rightarrow \mathscr{M} \end{equation}$$

Such that:

$$\begin{equation} \forall m \in \mathscr{M}, k \in \mathscr{K}: \mathbf{D}(k, \mathbf{E}(k, m)) = m \end{equation}$$

$\mathbf{E}$ is often randomized

$\mathbf{D}$ is always deterministic

A cipher $(\mathbf{E}, \mathbf{D})$ has perfect secrecy if:

$$\begin{equation} \forall m_{0}, m_{1} \in \mathscr{M} \, (|m_{0}| = |m_{1}|) \, and \, \forall c \in \mathscr{C} \\\ Pr[\mathbf{E}(k, m_{0}) = c] = Pr[\mathbf{E}(k, m_{1}) = c] \end{equation}$$

where $k \leftarrow \mathscr{K}$ (k is a randomly distributed key from $\mathscr{K}$)

In other words, if I was given a particular cipher text (encrypted message), I will have no idea which message originally created it since it could be any other message with equal probability.