1.3: Properties

A general-purpose security definition for encryption will be discussed in the next chapter. For now, we will show a simple but important property that one-time pad satisfies, and argue that it has some relevance to secure communication.

Imagine an eavesdropper who sees a single one-time pad ciphertext. The following algorithm describes what such an adversary will see if the plaintext happens to be m:

$\underline{\text{CTXT}(m \in \{0,1\}^{\lambda}):}\\\space\space k\space\leftarrow\space\space\{0,1\}^{\lambda}\\\space\space\space\text{return}\space k\oplus m\nonumber$

Since this algorithm involves random choices, its output on a particular m is not a fixed value but a random variable that follows some distribution. The important property of one-time pad has to do with this distribution:

Claim $$\PageIndex{1}$$

For every $$m\in \{0,1\}^{\lambda}$$ , the output distribution $$CTXT(m)$$ is the uniform distribution over $$\{0,1\}^{\lambda}$$.

Before proving the claim, let’s break down why it should have any relevance to security:

• An eavesdropper who intercepts a one-time pad ciphertext sees one sample of the distribution $$CTXT(m)$$, where m was the plaintext that was encrypted.
• Claim $$\PageIndex{1}$$ says that sampling from distribution $$CTXT(m)$$ is the same as sampling uniformly from $$\{0,1\}^{\lambda}$$ . The two subroutines merely describe two different methods to sample from the same mathematical distribution.

We can now say that, by intercepting a single ciphertext, an eavesdropper sees a uniform sample from $$\{0,1\}^{\lambda}$$.

• But the uniform distribution does not depend on $$m$$ at all! Truly, the intercepted ciphertext (at least by itself, without the corresponding key) can carry no information about $$m$$ if the same distribution can be achieved by ignoring $$m$$!

At this point you might be suspicious that I’m trying to talk you into a paradox: on one hand, the scheme satisfies the correctness property, so $$c$$ can always be decrypted to reliably obtain $$m$$. On the other hand, I want you to be convinced that $$c$$ carries no information whatsoever about $$m$$!

The answer to this riddle is that correctness is defined from the point of view of someone who knows the key $$k$$. Claim Claim $$\PageIndex{1}$$ is about the output distribution of the CTXT subroutine, which doesn’t contain $$k$$ (see Exercise 1.6). In short, if you know $$k$$, then c can be decrypted to obtain m; if you don’t know $$k$$, then $$c$$ might as well be uniformly distributed.

We now prove the claim:

Proof of Claim $$\PageIndex{1}$$

Fix $$m,c\in\{0,1\}^{\lambda}$$; what is the probability that $$CTXT(m)$$ produces output $$c$$? That event happens only when

$c=k\oplus m\space\Leftrightarrow\space k=m\oplus c.\nonumber$

The equivalence follows from the properties of XOR given in Section 0. We have fixed $$m$$ and $$c$$, and hence fixed the right-hand side of the last equation. In other words, after fixing $$m$$ and $$c$$, there is only one value of $$k$$ that encrypts $$m$$ to $$c$$ (that value being $$m\oplus c$$). Since CTXT chooses $$k$$ uniformly from $$?=\{0,1\}^{\lambda}$$, the probability of choosing the particular value $$k = m \oplus c$$ is $$1/2\lambda$$.

Limitations of One-Time Pad

The keys in one-time pad are as long as the plaintexts they encrypt. This is more or less unavoidable; see Exercise 2.4. Additionally, one-time pad keys can be used to encrypt only one plaintext (hence, “one-time” pad); see Exercise 1.5. Indeed, we can see that the CTXT subroutine in Claim Claim $$\PageIndex{1}$$ provides no way for a caller to guarantee that two plaintexts are encrypted with the same key, so it is not clear how to use Claim Claim $$\PageIndex{1}$$ to argue about what happens in one-time pad when keys are reused in this way.

Despite these limitations, one-time pad is the conceptual core for all forms of encryption we will discuss in this course. The only way to hide information, throughout all of cryptography, is to mask it with a uniformly chosen one-time pad.