A digital signature is a cryptographic protocol that is used to create unforgeable signatures for electronic messages. It can be used, for instance, to sign legal documents which can then be enforced in court. Central to the idea of a digital signature is the public key used to check it: usually, this is a number or set of numbers which is generally available, and which can be used to verify that a signature is correct. Anyone who has the public key can check the message, and will reach the same conclusion about whether the signature is valid or not. In addition, someone who just has the public key is unable to sign messages himself, or to change a signed message so that it says something else -- that power is reserved for the person who issued the public key.
However, classical methods of creating digital signatures rely on the fact that it is difficult to deduce the private key, which is used to create a signature, from the public key, which is used to verify it. For instance, the RSA encryption scheme can also be used to perform signatures, but only if the enemy is unable to factor large numbers. A forger with a quantum computer, for instance, could succesfully create false signed messages. The same problem arises when RSA is used for encoding secret information, and can be partially circumvented by quantum key distribution, so it is natural to ask if there is a way quantum states can help to create digital signatures.
In fact, there is: instead of having the public key be a string of classical bits, we let the public key be a number of quantum bits. Given n classical bits, there are only 2n possible values, and by looking at the string, we can tell exactly which one we have. There are many more possible states of n qubits, but any measurement can only learn n classical bits' worth of information about which one we have. It is even possible to cram a large number of possible quantum states into n qubits while keeping them pretty much separate from each other, so that if someone tells you which state you have, you can check that assertion. Nevertheless, without a hint, you would never be able to guess exactly which state you have; this remains true even if you have multiple copies of the state.
This means that we can let the public key be one of these many possible quantum states, chosen at random, while the private key says which of the states it is. Only the person who picked the state knows the private key, which enables them to sign messages without fear of having them forged.
There are substantial drawbacks to this approach, however. Most obviously, quantum states are more difficult to deal with than classical bit strings; in fact, the quantum processing and storage required for this scheme are just beyond the edge of current technology. Also, an enemy who gets too many copies of the public key will be able to figure out its identity, so to prevent this, the sender has to limit the number of copies she distributes. It is possible to make that number very large, however, so this is not too severe a restriction. Finally, the schemes we know are all very inefficient: a large public key is needed to sign even a single-bit message, and the key can only be used once. Hopefully, future research can eliminate this last problem.
For further information:
Back to Daniel Gottesman's home page
Created October 18, 2001