How to Sign Quantum Messages

Abstract

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.

51 pages

References in corpus (18)

• Quantum cryptography: Public key distribution and coin tossing
• The operational meaning of min- and max-entropy
• Random Oracles in a Quantum World
• Authentication of Quantum Messages
• Quantum Digital Signatures
• A Monogamy-of-Entanglement Game With Applications to Device-Independent Quantum Cryptography
• Pseudorandom States, Non-Cloning Theorems and Quantum Money
• Quantum commitments and signatures without one-way functions
• Unforgeable Quantum Encryption
• Computational Security of Quantum Encryption
• Semi-Quantum Money
• On Quantum Chosen-Ciphertext Attacks and Learning with Errors
• Quantum trapdoor functions from classical one-way functions
• Quantum Public-Key Encryption with Tamper-Resilient Public Keys from One-Way Functions
• Publicly verifiable quantum money from random lattices
• Revocable Quantum Digital Signatures
• On the (Im)plausibility of Public-Key Quantum Money from Collision-Resistant Hash Functions
• Encryption with Quantum Public Keys