For over 400 years, the problem remained.
How could Alice design a cipher that hides her fingerprint,
thus stopping the leak of information?
The answer is randomness.
Imagine Alice rolled a 26 sided die
to generate a long list of random shifts,
and shared this with Bob instead of a code word.
Now, to encrypt her message, Alice
uses the list of random shifts instead.
It is important that this list of shifts
be as long as the message, as to avoid any repetition.
Then she sends it to Bob, who decrypts the message using
the same list of random shifts she had given him.
Now Eve will have a problem, because the resulting
encrypted message will have two powerful properties.
One, the shifts never fall into a repetitive pattern.
And two, the encrypted message will have a uniform frequency
distribution.
Because there is no frequency differential and therefore
no leak, it is now impossible for Eve
to break the encryption.
This is the strongest possible method of encryption,
and it emerged towards the end of the 19th century.
It is now known as the one-time pad.
In order to visualize the strength of the one-time pad,
we must understand the combinatorial explosion
which takes place.
For example, the Caesar Cipher shifted every letter
by the same shift, which was some number between 1 and 26.
So if Alice was to encrypt her name,
it would result in one of 26 possible encryptions.
A small number of possibilities, easy to check them all,
known as brute force search.
Compare this to the one-time pad, where each letter would
be shifted by a different number between 1 and 26.
Now think about the number of possible encryptions.
It's going to be 26 multiplied by itself five times, which
is almost 12 million.
Sometimes it's hard to visualize,
so imagine she wrote her name on a single page,
and on top of it stacked every possible encryption.
How high do you think this would be?
With almost 12 million possible five-letter sequences,
this stack of paper would be enormous,
over one kilometer high.
When Alice encrypts her name using the one-time pad,
it is the same as picking one of these pages at random.
From the perspective of Eve, the code breaker,
every five letter encrypted word she
has is equally likely to be any word in this stack.
So this is perfect secrecy in action.