|
Cryptography is not hard, in principle.
All you need is a message,
and a string of random characters the same length as the message.
These days, it is most convenient to represent the message
in electronic form, so it is a long string of binary digits
(bits), and the random sequence likewise.
Exclusive-OR
each bit of the message with the corresponding
bit of the random sequence, and you have a random-looking
binary mess that is guaranteed unbreakable.
The only way to get the message back is to exclusive-OR the
hash with the same random bit sequence.
Oh, yes: each random sequence must be used only once.
If it is used for more than one message, there is a chance
that an eavesdropper could find patterns in the messages and
decode them, and learn your secrets.
For this reason, the sequences are called
one-time pads.
They used to be actually
written on pads of paper,
and each sheet would be burned after it had been used once.
There had to be at least two identical pads, one for the
sender and one for each receiver of the coded message.
Much effort used to go into
hiding,
finding, and stealing these pads.
Modern methods of cryptography are based on ways to
create random-looking one-time pads, in a way that can be
repeated (so that the recipient can re-create the pad and
get the message back).
But if you can re-create the pad, then it is not really
random, and somebody might be able to figure out how to
re-create the pad and "steal" your message.
And if the sequence is really random, then by definition
there is no way to re-create it.
What is needed, is a way to create a truly random sequence
twice: once for the sender once and for the receiver, with
no chance that anyone could intercept or alter either copy.
Enter quantum cryptography.
Quantum cryptography dates back at least to 1970, when
Stephen Wiesner wrote a paper about it.
The paper was so unorthodox that it was not published until
1983.
Much work has been done since then, by many people, and
there are a number of ideas for using quantum mechanics
with cryptography.
We are going to illustrate one idea using quantum tic-tac-toe.
As mentioned, the sender and receiver must each get a copy
of the same one-time pad.
It would be safest to generate it immediately before use,
so neither party has to keep the pad safe and unseen.
We can do that using entangled particles, if we can arrange
that the sender gets one particle, the receiver
gets its entangled partner, and they can both measure the
property that is entangled.
For our illustration, we are going to have Alice and Bob
play a set of quantum tic-tac-toe games, over and
over.
The entangled particles are just the spooky marks.
The measurement happens when an entanglement collapses into
real marks.
At the end of each game, Alice looks at square 1, Bob looks
at square 9, and each gets one bit for their one-time pad.
When they have played enough games to "cover" the message,
Alice can encrypt it and send it, and Bob can decrypt it.
The first four moves of the games are always the same,
as shown below.
The next two moves, 5 and 6, will merge the two entanglements
in squares 2/1/4 and squares 6/9/8, and collapse them.
It should be noted that Alice and Bob are not
playing to win; in particular, they choose randomly
which way to collapse the entanglement each time.
That way, they get a genuine random one-time pad.
|
