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

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.