Roughly speaking, the purpose of a cryptographic protocol is to perform some task involving multiple people without letting anyone involved learn any privileged information, and, as far as possible, without being disrupted by people attempting to cheat. The prototypical cryptographic task is sending a secret message from Alice to Bob without a third party, Eve, learning what the message is. The standard classical methods for solving this problem rely on Eve having only limited computational power. For instance, RSA, a commonly used scheme, relies on Eve not being able to factor large numbers. But what if Eve has some secret device that enables her to do so? (For instance, factoring can be done efficiently on a quantum computer; or she might have some particularly clever classical algorithm.)
To remove this assumption about Eve's computational power, Alice and Bob need to share a secret key, about which Eve knows nothing at all. The key needs to be as long as the message to be sent. Alice encodes the message using the key, and sends it to Bob, who decodes it. Since Eve knows nothing about the key, she can learn nothing about the message. The key cannot be used again, however, or Eve might be able to guess some information about it by comparing the two messages. This protocol is called a one-time pad.
The one-time pad relies on Alice and Bob having a large secret key, or they will quickly run out. They could renew their key by having a meeting somewhere safe from Eve and exchanging codebooks with long lists of keys. However, frequently an actual physical meeting is impractical, and it would be desireable to be able to renew the key using only public communications. One possible method for doing so is quantum key distribution, which involves sending non-orthogonal quantum states from Alice to Bob.
There are many other applications of quantum mechanics to cryptography, which tend to come in three flavors:
Even if we restrict ourselves to protecting classical information, there are many different types of cryptographic protocol. For instance, a digital signature scheme allows Alice to send a message to Bob in such a way that Bob can verify that the message is really from Alice and that it has not been altered at all. A zero-knowledge proof allows Alice to prove to Bob that she knows how to solve some problem without Bob learning anything about how Alice's solution works. A secure computation allows two or more people to compute some function based on all of their inputs, without any of them learning any more about the others' inputs than implied by the value of the function.
There are classical solutions to all of the above problems, but all rely on making some sort of assumption, about the computational power of a cheater, about the number of cheaters, or something of this kind. Based on quantum key distribution, one might hope that a quantum computer might allow us to weaken or remove these assumptions. For instance, it is possible to make a quantum digital signature which is secure against all attacks allowed by quantum mechanics.
Many classical cryptographic protocols work by building up the protocol from simpler protocols. One particularly useful simple protocol is called bit commitment. In a bit commitment protocol, Alice chooses a bit (possibly at random), and sends some proof of her choice to Bob. However, due to the nature of the proof, Bob cannot figure out what Alice's bit is until she tells him, but once she does, Bob can easily verify that she is telling the truth. A simple example of bit commitment would be if Alice writes her choice on a piece of paper and puts it in a locked box, which she gives to Bob. Bob cannot open the box until Alice gives him the key, but Alice cannot change her choice once she has given the box to Bob.
Standard classical cryptographic protocols for bit commitment rely on Bob having limited computational power. For a while, it was thought quantum bit commitment protocols existed which were unconditionally secure. However, it turns out that if Alice and Bob have quantum computers, any protocol for which Bob cannot determine the value of Alice's bit allows Alice to safely change the bit without Bob finding out.
This was a great disappointment, and later results proved that many other quantum cryptographic protocols were also impossible. However, there are still a number of possible protocols that have not been ruled out, including some of considerable interest. Quantum computation may allow us to perform some of these operations more safely than any classical protocol.
For further information:
Back to Daniel Gottesman's home page
Updated: September 5, 2003