Perfect Secrecy

Introduction

Perfect secrecy provides security against a limited variant of the ciphertext-only attack (COA) where the adversary is presented with only a single ciphertext - no more, no less. It was first described by the father of information theory - Claude Shannon who realised that for a cipher to be invulnerable to a single-COA attack (i.e. a ciphertext-only attack with a single ciphertext), the ciphertext must not reveal anything about the underlying plaintext.

Definition: Perfect Secrecy

An encryption scheme $(\text{Enc},\text{Dec})$ is perfectly secret if for every subset $M\subseteq \mathcal{M}$ and for every strategy employed by the adversary Eve, if the plaintext $m\in M$ was chosen at uniformly at random and was encrypted with a uniformly random key $k\in \mathcal{K}$, then the probability that Eve can guess the plaintext when knowing its ciphertext $c={\text{Enc}}_k(m)$ is at most $\frac{1}{|M|}$.

INTUITION

When stripped of its mathematical coating, the definition is pretty simple. A plaintext is chosen at random from a set of plaintexts $M$, which is a subset of the message space. There are $|M|$ possible messages for this choice, so the chance that Eve can guess the chosen message without having seen its ciphertext is $\frac{1}{|M|}$. The premise behind perfect secrecy is that this holds true even if Eve does have access to the ciphertext - Eve should not be able to obtain any information from the ciphertext that would improve her chances of guessing the chosen plaintext.

Determining whether a given encryption scheme is perfectly secret might prove tricky when using this definition. Fortunately, there are some properties which can come in handy - every perfectly secret cipher has them and if a given encryption scheme has one of these properties, then it is perfectly secret and by extension has all of these properties (what are known as “if and only if” conditions).

Theorem: Perfect Secrecy Equivalent Definitions

Since these properties go both ways - every perfectly secret cipher has these and every cipher which has one of these has all of them and is perfectly secret, they are called equivalent definitions.

For any perfectly secret encryption scheme $(\text{Enc},\text{Dec})$, it is true that:

1. For every two distinct plaintexts $m_0,m_1\in \mathcal{M}$ and any strategy employed by the adversary $\text{Eve}:\mathcal{C}\to \mathcal{M}$, if Eve is given a ciphertext of one of the plaintexts $m_0$ or $m_1$, then the probability that Eve can guess the message the ciphertext belongs to is less than or equal to $\frac{1}{2}$, i.e.

$$\underset{b{\leftarrow }_R\{0,1\},k{\leftarrow }_R\mathcal{K}}{\mathrm{Pr}}[\text{Eve}({\text{Enc}}_k(m_b))=m_b]\le \frac{1}{2}$$

2. For every two fixed plaintexts $m,m^{\prime }\in \mathcal{M}$, the distributions $\{{\text{Enc}}_k(m){\}}_{k{\leftarrow }_R\mathcal{K}}$ and $\{{\text{Enc}}_k(m^{\prime }){\}}_{k{\leftarrow }_R\mathcal{K}}$ obtained by sampling the key space $\mathcal{K}$ are identical.

3. For every distribution $\mathcal{D}$ over $\mathcal{M}$ and strategy $\text{Eve}:\mathcal{C}\to \mathcal{M}$, the probability that Eve can guess a message chosen according to $\mathcal{D}$ from its corresponding ciphertext is less than or equal to the highest probability assigned by the distribution $\mathcal{D}$, i.e.

$$\underset{m{\leftarrow }_R\mathcal{D},k{\leftarrow }_R\mathcal{K}}{\mathrm{Pr}}[\text{Eve}({\text{Enc}}_k(m))=m]\le \max (\mathcal{D})$$

PROOF

Proof of the first property:

If a Shannon cipher $(\text{Enc},\text{Dec})$ is perfectly secret, then the first property follows directly from the definition of perfect secrecy.

To prove the “if” direction we use a proof by contradiction. We need to show that if there were some set of plaintexts $M\subseteq \mathcal{M}$ and a strategy for Eve to guess a chosen plaintext from $M$ with a probability greater than $\frac{1}{|M|}$ (i.e., the cipher were not perfectly secret), then there would also exist a set $M^{\prime }$ of size 2 for which Eve can guess a plaintext chosen from $M^{\prime }$ with probability greater than $\frac{1}{2}$.

Essentially, this set would be $M^{\prime }=\{m_0,m_1\}$ for some plaintexts $m_0$ and $m_1$ such that $\mathrm{Pr}[\text{Eve}({\text{Enc}}_k(m_1))=m_1]>\mathrm{Pr}[\text{Eve}({\text{Enc}}_k(m_1))=m_0]$.

To do this, fix $m_0$ to be the message of all 0s and pick a message $m_1$ uniformly at random from $M$. Under our assumption, for any $k$, it is true that

$$\underset{m_1{\leftarrow }_{R}M}{\mathrm{Pr}}[\text{Eve}({\text{Enc}}_k(m_1))=1]>\frac{1}{|M|}$$

This can also be rewritten as

$$\underset{m_1{\leftarrow }_{R}M}{\mathbb{E}}\mathrm{Pr}[\text{Eve}({\text{Enc}}_k(m_1))=1]>\frac{1}{|M|}$$

On the other hand, the string $m^{\prime }=\text{Eve}({\text{Enc}}_k(m_0))$ does not depend on $m_1$ for any choice of the key $k$, so if $m_1$ is selected uniformly at random from $M$, then the probability that $m_1=m^{\prime }$ is $\frac{1}{|M|}$.

$$\underset{m_1{\leftarrow }_{R}M}{\mathrm{Pr}}[m_1=m^{\prime }]=\frac{1}{|M|}$$

This can also be rewritten as

$$\underset{m_1{\leftarrow }_{R}M}{\mathbb{E}}\mathrm{Pr}[m_1=m^{\prime }]=\frac{1}{|M|}$$

Now, by linearity of expectation

$$\underset{m_1{\leftarrow }_{R}M}{\mathbb{E}}(\mathrm{Pr}[\text{Eve}({\text{Enc}}_k(m_1))=m_1]-\mathrm{Pr}[\text{Eve}({\text{Enc}}_k(m_0))=m_0])>0$$

By the averaging argument, there must exist some $m_1$ for which $\mathrm{Pr}[\text{Eve}({\text{Enc}}_k(m_1))=m_1]>\mathrm{Pr}[\text{Eve}({\text{Enc}}_k(m_1))=m_0]$.

In other words, we just proved the existence of two messages $m_0,m_1$ for which $\mathrm{Pr}[\text{Eve}({\text{Enc}}_k(m_1))=m_1]>\mathrm{Pr}[\text{Eve}({\text{Enc}}_k(m_1))=m_0]$ and can now construct the set $M^{\prime }=\{m_0,m_1\}$ which contradicts our initial condition. Therefore, $M^{\prime }$ cannot exist and by extension $M$ cannot either, making the cipher perfectly secret.

Proof of Second Property TODO

Proof of Third Property TODO

Now, these properties are useful, but does there actually exist a perfectly secret encryption scheme? The answer to that is yes and perhaps the most famous example of such a cipher is the One-Time Pad.

Long Keys Requirement

Perfect secrecy does impose one huge restriction - for an encryption scheme to be perfectly secret, its key cannot have a length shorter than that of the message.

Theorem: Long Keys Requirement

For every perfectly secret encryption scheme $(\text{Enc},\text{Dec})$, the message length function $l(n)$ satisfies $n\ge l(n)$.

PROOF

Given a Shannon cipher $(\text{Enc},\text{Dec})$, if the key was shorter than the message, then there would be fewer possible keys than possible messages, i.e. $|\mathcal{K}|<|\mathcal{M}|$. An adversary can gain an edge by choosing a key instead of a plaintext at random and simply decrypting the known ciphertext $c$ with it. The probability that the decrypted ciphertext results in the hidden message $m$, i.e. $\mathrm{Pr}[{\text{Dec}}_k(c)=m]$, will be $\frac{1}{|K|}$ and since there are fewer keys than messages, this probability is greater than $\frac{1}{|M|}$, thus making the cipher not perfectly secret.

In proving the theorem, we have actually proved the following, more general statement.

WARNING

For a Shannon cipher to be perfectly secret, the number of possible keys must be greater than or equal to the number of possible messages, i.e. $|\mathcal{K}|\ge |\mathcal{M}|$.

The aforementioned relationship between the key and message lengths is just a corollary of this. This is a profound fact which limits the practicality of perfect secrecy. For example, if one wanted to securely transmit a 1 GB file using a perfectly secret encryption scheme, then they would also require a 1 GB key!

In conclusion, perfect secrecy is an amazing (and even implementable!) idea, but it is not practical. Due to this fact, perfectly secret ciphers are rarely employed in practice. Instead, relaxed security notions which are still good enough are used. As with most things in life, one cannot have their cake and eat it, too.