Can you sign a quantum state?
arXiv:1811.11858 · doi:10.22331/q-2021-12-16-603
Abstract
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.
arXiv comment26+12 pages, v4: version for publication in Quantum, v5: CC license
References in corpus (12)
- Coding Theorem and Strong Converse for Quantum Channels
- Authentication of Quantum Messages
- Quantum homomorphic encryption for circuits of low -gate complexity
- Interactive Proofs For Quantum Computations
- Secure two-party quantum evaluation of unitaries against specious adversaries
- Unforgeable Quantum Encryption
- Quantum authentication with key recycling
- Computational Security of Quantum Encryption
- Efficient Simulation for Quantum Message Authentication
- Quantum non-malleability and authentication
- The Universal Composable Security of Quantum Message Authentication with Key Recyling
- Composable and Finite Computational Security of Quantum Message Transmission