  Signing quantum messages has long been considered impossible even under
computational assumptions. In this work, we challenge this notion and provide
three innovative approaches to sign quantum messages that are the first to
ensure authenticity with public verifiability. Our contributions can be
summarized as follows:
  1) We introduce the concept of time-dependent (TD) signatures, where the
signature of a quantum message depends on the time of signing and the
verification process depends on the time of the signature reception. We
construct this primitive assuming the existence of post-quantum secure one-way
functions (pq-OWFs) and time-lock puzzles (TLPs).
  2) By utilizing verification keys that evolve over time, we eliminate the
need for TLPs in our construction. This leads to TD signatures from pq-OWFs
with dynamic verification keys.
  3) We then consider the bounded quantum storage model, where adversaries are
limited with respect to their quantum memories. We show that quantum messages
can be signed with information-theoretic security in this model.
  Moreover, we leverage TD signatures to achieve the following objectives,
relying solely on pq-OWFs: (a) We design a public key encryption scheme
featuring authenticated quantum public keys that resist adversarial tampering.
(b) We present a novel TD public-key quantum money scheme.
