  Cryptography with quantum states exhibits a number of surprising and
counterintuitive features. In a 2002 work, Barnum et al. argue that these
features imply that digital signatures for quantum states are impossible
(Barnum et al., FOCS 2002). In this work, we ask: can all forms of signing
quantum data, even in a possibly weak sense, be completely ruled out? We give
two results which shed significant light on this basic question.
  First, we prove an impossibility result for digital signatures for quantum
data, which extends the result of Barnum et al. Specifically, we show that no
nontrivial combination of correctness and security requirements can be
fulfilled, beyond what is achievable simply by measuring the quantum message
and then signing the outcome. In other words, only classical signature schemes
exist.
  We then show a positive result: a quantum state can be signed with the same
security guarantees as classically, provided that it is also encrypted with the
public key of the intended recipient. Following classical nomenclature, we call
this notion quantum signcryption. Classically, signcryption is only interesting
if it provides superior performance to encypt-then-sign. Quantumly, it is far
more interesting: it is the only signing method available. We develop
"as-strong-as-classical" security definitions for quantum signcryption and give
secure constructions based on post-quantum public-key primitives. Along the
way, we show that a natural hybrid method of combining classical and quantum
schemes can be used to "upgrade" a secure classical scheme to the fully-quantum
setting, in a wide range of cryptographic settings including signcryption,
authenticated encryption, and CCA security.
