Suppose Alice wants to send a message to Bob. The message is important but not necessarily secret -- perhaps the text of a news article, for instance. Bob wants to be sure that he receives the same article that Alice sent, and that it hasn't been altered at all by some enemy of theirs, Eve. He wants to rule out both big changes, like replacing the article with a completely different one, and small ones, such as changing the number 154 to 954. Eve, unfortunately, may control the communications channel between Alice and Bob, so she controls what Bob receives. His goal is to tell, when he receives a message, if it came from Alice or from Eve. Of course Eve, if she desires, can always block Bob from getting a message, but Bob wishes to never be deceived into thinking a message comes from Alice when it really comes from Eve.
This task, when applied to classical messages, is a kind of cryptographic task called authentication. It can be done with complete security, provided Alice and Bob share a secret key which is unknown to Eve. Then Alice and Bob use the key k to determine some function fk. Instead of sending the message m, Alice sends (m,fk(m)). Bob, when he receives (m', s), checks that s = fk (m'). Since Eve doesn't know the key k, she unlikely to be able to guess the right function fk or the right value s to apply to a new message m', and so if s and m match, Bob can be highly confident the message really came from Alice and has not been altered by Eve. Designing a good authentication protocol is mostly a matter of choosing a good set of functions fk: If the class is too small, Eve can sometimes guess s without knowing k, while if the class is large, a long secret key is required to specify the correct function.
A similar task to authentication is called a digital signature. A digital signature uses public key cryptography and allows not only Bob to verify that a message came from Alice, but anyone who knows Alice's public key. Public key cryptography, however, usually relies on computational assumptions to make it work; quantum mechanics can be used to provide unconditional secure quantum signatures.
If Alice wants to send quantum information to Bob instead of classical information, standard classical authentication techniques will no longer work to prevent Eve from altering the quantum state. In particular, an authentication protocol for quantum states must protect superpositions of states, and the quantum state |0> + |1> is different from the quantum state |0> - |1>.
To protect quantum states from a would-be forger, we need a quantum authentication scheme. Again, Alice and Bob share a secret key k unknown to Eve. The basic idea of a quantum authentication protocol is to encode the quantum state in a quantum error-correcting code; actually, a quantum error-detecting code is sufficient here, since Bob only cares about detecting tampering by Eve, not about fixing it, which is not possible in general. However, if Alice and Bob use the same code all of the time, Eve can simply create errors that the code cannot detect, so they must use one of a family of codes which detect different kinds of errors. The key k tells them which code to use. Since Eve doesn't know k, she doesn't know which errors the code detects, and no matter what she tries to do, she has a good chance of getting caught.
It turns out that this is not enough to create a quantum authentication scheme: Alice and Bob must also encrypt the quantum state. Note that this was not at all necessary for a classical authentication scheme, and it is quite possible to create a classical authentication scheme where Eve can read the message, but not change it. In the quantum case, however, reading or measuring the value of a state necessarily changes it, and if Eve can distinguish the message for |0> from the message for |1>, she can change the message |0> + |1> to the message |0> - |1>. It turns out that she can do this without getting caught, no matter what quantum authentication scheme Alice and Bob try to use, unless Eve, not knowing the key k, is unable to learn any information about the quantum state being transmitted. That is, Alice and Bob must also use k to encrypt the quantum state. If they do so, and choose one from a family of quantum error-detecting codes as described above, they can successfully authenticate a quantum message from Alice to Bob without fear that it has been at all changed by Eve.
Quantum authentication schemes are fairly useful. Not only can they be used to reliably send quantum information through an untrusted channel, they also offer advantages for sending classical information. Since a quantum authentication scheme both encrypts and authenticates quantum information, clearly it also encrypts and authenticates classical information sent via the protocol. This much could be done with purely classical techniques, but the quantum authentication protocol offers an additional property impossible in the classical world: the adversary Eve is unable to copy the message during transmission. That is, a quantum authentication scheme also provides uncloneable encryption.
For further information:
Back to Daniel Gottesman's home page
Created: September 5, 2003