We present a quantum digital signature scheme whose security
is based on fundamental principles of quantum physics.
It allows a sender (Alice) to sign a message in such a way
that the signature can be validated by a number of different
people, and all will agree either that the message came from
Alice or that it has been tampered with. To accomplish this
task, each recipient of the message must have a copy of Alice’s
“public key,” which is a set of quantum states whose
exact identity is known only to Alice. Quantum public keys
are more difficult to deal with than classical public keys: for
instance, only a limited number of copies can be in circulation,
or the scheme becomes insecure. However, in exchange
for this price, we achieve unconditionally secure digital signatures.
Sending an m-bit message uses up O(m) quantum
bits for each recipient of the public key. We briefly discuss
how to securely distribute quantum public keys, and show
the signature scheme is absolutely secure using one method
of key distribution. The protocol provides a model for importing
the ideas of classical public key cryptography into
the quantum world.