TY - GEN

T1 - One-shot signatures and applications to hybrid quantum/classical authentication

AU - Amos, Ryan

AU - Georgiou, Marios

AU - Kiayias, Aggelos

AU - Zhandry, Mark

N1 - Funding Information:
We thank the anonymous reviewers for their helpful remarks and comments. The second author is supported by the National Science Foundation (NSF), under Grant 40D03-00-01. The third author was partly supported by EU Project No. 780477, PRIVILEDGE and EU Project No. 780108, FENTEC. The fourth author is supported by an NSF CAREER award.

PY - 2020/6/8

Y1 - 2020/6/8

N2 - 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.

AB - 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.

KW - Hybrid Quantum Cryptography

KW - One-Shot Signatures

KW - Quantum Money

UR - http://www.scopus.com/inward/record.url?scp=85086769846&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85086769846&partnerID=8YFLogxK

U2 - 10.1145/3357713.3384304

DO - 10.1145/3357713.3384304

M3 - Conference contribution

AN - SCOPUS:85086769846

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 255

EP - 268

BT - STOC 2020 - Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing

A2 - Makarychev, Konstantin

A2 - Makarychev, Yury

A2 - Tulsiani, Madhur

A2 - Kamath, Gautam

A2 - Chuzhoy, Julia

PB - Association for Computing Machinery

T2 - 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020

Y2 - 22 June 2020 through 26 June 2020

ER -