Paper 2020/107

One-shot Signatures and Applications to Hybrid Quantum/Classical Authentication

Abstract

We define the notion of one-shot signatures, which are signatures where any secret key can be used to sign only a single message, and then self-destructs. While such signatures are of course impossible classically, we construct one-shot signatures using quantum no-cloning. In particular, we show that such signatures exist relative to a classical oracle, which we can then heuristically obfuscate using known indistinguishability obfuscation schemes. We show that one-shot signatures have numerous applications for hybrid quantum/classical cryptographic tasks, where all communication is required to be classical, but local quantum operations are allowed. Applications include one-time signature tokens, quantum money with classical communication, decentralized blockchain-less cryptocurrency, signature schemes with unclonable secret keys, non-interactive certifiable min-entropy, and more. We thus position one-shot signatures as a powerful new building block for novel quantum cryptographic protocols.

Note: There is a bug in our proof of security for one-shot signatures relative to the classical oracle, pointed out to us by James Bartusek. Thus bug seems fundamental, and likely cannot be fixed without new ideas. This does not indicate any actual attack on our construction, which still remains plausibly secure. It also does not affect any of our applications of one-shot signatures. We leave the paper unchanged including the faulty proof of security for future reference.