Paper 2017/1080

Quantum Lightning Never Strikes the Same State Twice

Mark Zhandry

Abstract

Public key quantum money can be seen as a version of the quantum no-cloning theorem that holds even when the quantum states can be verified by the adversary. In this work, investigate quantum lightning, a formalization of ``collision-free quantum money'' defined by Lutomirski et al. [ICS'10], where no-cloning holds even when the adversary herself generates the quantum state to be cloned. We then study quantum money and quantum lightning, showing the following results: - We demonstrate the usefulness of quantum lightning beyond quantum money by showing several potential applications, such as generating random strings with a proof of entropy, to completely decentralized cryptocurrency without a block-chain, where transactions is instant and local. - We give win-win results for quantum money/lightning, showing that either signatures/hash functions/commitment schemes meet very strong recently proposed notions of security, or they yield quantum money or lightning. Given the difficulty in constructing public key quantum money, this suggests that natural schemes do attain strong security guarantees. - We show that instantiating the quantum money scheme of Aaronson and Christiano [STOC'12] with \emph{indistinguishability obfuscation} that is secure against quantum computers yields a secure quantum money scheme. This construction can be seen as an instance of our win-win result for signatures, giving the first separation between two security notions for signatures from the literature. - Finally, we give a plausible construction for quantum lightning, which we prove secure under an assumption related to the multi-collision resistance of degree-2 hash functions. Our construction is inspired by our win-win result for hash functions, and yields the first plausible standard model instantiation of a non-collapsing collision resistant hash function. This improves on a result of Unruh [Eurocrypt'16] which is relative to a quantum oracle. Thus, we provide the first constructions of public key quantum money from several cryptographic assumptions. Along the way, we develop several new techniques including a new precise variant of the no-cloning theorem.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint. Minor revision.
Keywords
quantum cryptographyquantum money
Contact author(s)
mzhandry @ princeton edu
History
2018-08-14: last of 2 revisions
2017-11-10: received
See all versions
Short URL
https://ia.cr/2017/1080
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/1080,
      author = {Mark Zhandry},
      title = {Quantum Lightning Never Strikes the Same State Twice},
      howpublished = {Cryptology ePrint Archive, Paper 2017/1080},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/1080}},
      url = {https://eprint.iacr.org/2017/1080}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.