Uncloneable Encryption

If Alice wishes to send a secret message to Bob, she encrypts it, rendering it effectively into gibberish to a would-be eavesdropper Eve. Bob, however, knows a key which can be used decrypt the message, restoring it to a readable form. There are many different kinds of encryption schemes, which are the best-known variety of cryptographic task. Some are stronger than others. Many use the same decryption key over and over again, and rely on Eve's inability to solve some computationally difficult problem. It is even possible to create a completely unbreakable encryption scheme, the one-time pad, which unfortunately requires a long key, as long as the message being sent, and only allows the key to be used once.

One problem with computationally secure encryption is that Eve can simply copy down the encrypted message and then try to break it at her leisure. For instance, she might apply brute-force methods, running many computers for a long time, or wait for faster or better computers. For example, a quantum computer could break many of today's standard codes. Or Eve might wait for a breakthrough in cryptoanalysis techniques which might make breaking the code easy. Alternatively, Eve might try to steal Bob's key or hope that he will carelessly leave it unguarded. Even the one-time pad is vulnerable to this last problem, meaning it is critical to utterly destroy a one-time pad key after using it.

However, quantum states have an interesting property: they cannot be copied (a result known as the "no-cloning theorem"). It turns out to be possible to give this property to encrypted classical messages, creating something known as uncloneable encryption. An unencrypted classical message can always be copied, so there is no such thing as quantum copy protection; indeed, reading a message (or watching it, listening to it, etc.) is in a very real sense making a copy. However, uncloneable encryption is possible, meaning the eavesdropper Eve, who cannot read the message, can also not copy it for later decoding. Thus, information protected by an uncloneable encryption scheme remains secure even if the scheme itself later becomes unreliable -- for instance, if Eve learns how to solve the computational problem it relies on, or even if she steals Bob's decryption key.

One way to perform uncloneable encryption is to use a quantum authentication scheme. A quantum authentication scheme is normally used to protect quantum information from being changed, but could also protect classical information. Not only must a quantum authentication scheme encrypt the information it protects, but it also provides uncloneable encryption.

An uncloneable encryption scheme, in turn, can be used to perform quantum key distribution, that is, to generate new classical secret key over an insecure quantum channel. Alice simply chooses a random number r and uses this as a key for an uncloneable encryption scheme, with which she transmits another random number k to Bob. At this point, neither Eve nor Bob knows r, so neither can learn k. Bob lets Alice know when he has received the transmitted message, however, and by the uncloneability property, Alice and Bob know that Eve canot have copied the message in transmission. It is therefore safe for Alice to publicly announce r. Eve has lost her chance at decrypting the message: she cannot learn k, but Bob can. Alice and Bob therefore both know the random number k, but Eve does not, so k becomes their new secret key.

For further information:


Back to Daniel Gottesman's home page

Created: September 5, 2003