> For the complete documentation index, see [llms.txt](https://shai-deshe.gitbook.io/understanding-blockdags-and-ghostdag/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://shai-deshe.gitbook.io/understanding-blockdags-and-ghostdag/supplementary-material/computer-science/page-3/one-time-pads.md).
# One Time Pads
TODO: rewrite after the structure of the appendix is clearer
A *one time pad* is possibly the first encryption protocol that is actually secure in some modern sense. The idea is very simple, and we can demonstrate it for images.
Say you and I want to send each other an encrypted $$100\times 100$$ image at some time in the future. We prepare for this by meeting up, and flipping $$100\cdot 100$$ coins. We encode the results of our coin flips into a $$100\times 100$$ image, with a black pixel for heads and a white pixel for tails, resulting in a picture somewhat like this:
Such a picture is called a *one-time pad*. We both keep a copy of this image, so we can use it to send an encrypted message.
How do we do so? Well, say I drew this circle:
and it made me feel accomplished and excited, so I want to share it with you. But given how perfect this circle is, I don't want anyone else to see it yet. I can take our one time pad and do the following: for any *black* pixel in the pad, *change the color* of the corresponding pixel in my drawing, and send the result. In our case it would look like this:
As you can see, it does not look extremely different than the secret-key, and for a good reason. Recall that the original key was *random*. So essentially, what I did is *exactly the same* as flipping a coin ten-thousand times on the spot to choose what pixels to flip. Now here's the gist: doing this will result in *completely random noise* regardless of what the initial image was. It doesn't matter. Each pixel is still equally likely to be either black or white.
The symmetry between you, who is supposed to decrypt the message, and the eavesdropper who tries to recover it, is that *you know the results of the coin flips*. Without this information, there is *nothing* that can be recovered from the cipher.
OK, so that sounds terrific, right? An encryption protocol that is secure against arbitrary adversaries, no matter how powerful, what more can you want?
Well, there is a reason it is called a *one-time pad*. Say that tomorrow you draw this beautiful square:
and you want to share it with me. Problem: I already used the pad to send you the circle. What happens if you disregard this and use the same pad to send me the square? Well, the encrypted square looks like this:
which also looks like a random pile of garbage, so the attacker never saw our key and only got access to two piles of garbage, where's the problem here?
Well, while it is true that *each separate* cipher looks like garbage, the ciphers are actually *correlated*: they both got their randomness from the same source. In particular, the *same coin flips* were used for both. So what happens if we use *one of the images* on the other? That is, for each black pixel in the first cipher, we flip the corresponding pixel in the second cipher?
Consider a single pixel. If it had the same color on both images, then it will have the same color in both ciphers, so it will be *white* on the result. Similarly, if it was different colors on both images, it will have different colors in both ciphers, so it will be *black* on the result. The upshot is that by taking two ciphers and flipping one according to the other, we learn *where the original messages were the same, and where they were different*. While that does not reveal the cipher *completely* (for example, if you invert both image you would get the same result), it leaks quite a bit of knowledge:
An attacker can use this knowledge to correctly guess portions of the secret key, making our scheme very insecure for using more than once.
So we find the disadvantage in one-time pads, that they are *one time*. Consequentally, the secret-key must be at least as large as all messages you intend to send *combined*.
{% hint style="info" %}
This is a special case of a more general theorem, stating that any *information theoretically secure* encryption schemes *must* have secret-key as long as the *combined* length of messages that can be sent securely
{% endhint %}
