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.