How to Sign Quantum Messages

Signing quantum messages was proven to be impossible even under computational assumptions. We realize that this result can be circumvented if the signing procedure varies with respect to some dimension. Specifically, we provide two approaches to sign quantum messages that are the first to ensure authenticity with public verifiability: (1) We construct a notion we term time-dependent signatures assuming one-way functions. In this setting, the signature of a message depends on the time it is signed and, as a result, the verification procedure depends on the time that the signature is received. The keys are classical but the verification key needs to be continually updated. (2) We construct an information-theoretically secure signature scheme in the bounded quantum storage model where adversaries have bounded quantum memories. Our scheme can be made secure against adversaries with arbitrarily large quantum memories by increasing the size of the transmissions sufficiently, while honest users only need $O(\ell^2)$ quantum memory where $\ell$ is the size of the plaintext quantum messages. Furthermore, we apply our time-dependent signatures to perform the following tasks assuming only one-way functions: (a) Construct a quantum public key encryption scheme with authenticated quantum public keys which resist adversarial tampering. (b) Build a public-key quantum money scheme with unforgeable, unclonable, and publicly verifiable banknotes that have a limited lifespan.