Paper 2023/069

On the (Im)plausibility of Public-Key Quantum Money from Collision-Resistant Hash Functions

Prabhanjan Ananth, University of California, Santa Barbara
Zihan Hu, Tsinghua University
Henry Yuen, Columbia University
Abstract

Public-key quantum money is a cryptographic proposal for using highly entangled quantum states as currency that is publicly verifiable yet resistant to counterfeiting due to the laws of physics. Despite significant interest, constructing provably-secure public-key quantum money schemes based on standard cryptographic assumptions has remained an elusive goal. Even proposing plausibly-secure candidate schemes has been a challenge. These difficulties call for a deeper and systematic study of the structure of public-key quantum money schemes and the assumptions they can be based on. Motivated by this, we present the first black-box separation of quantum money and cryptographic primitives. Specifically, we show that collision-resistant hash functions cannot be used as a black-box to construct public-key quantum money schemes where the banknote verification makes classical queries to the hash function. Our result involves a novel combination of state synthesis techniques from quantum complexity theory and simulation techniques, including Zhandry's compressed oracle technique.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint.
Keywords
quantum cryptographyquantum moneyblack-box separations
Contact author(s)
prabhanjan @ cs ucsb edu
huzh19 @ mails tsinghua edu cn
hyuen @ cs columbia edu
History
2023-01-23: approved
2023-01-21: received
See all versions
Short URL
https://ia.cr/2023/069
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2023/069,
      author = {Prabhanjan Ananth and Zihan Hu and Henry Yuen},
      title = {On the (Im)plausibility of Public-Key Quantum Money from Collision-Resistant Hash Functions},
      howpublished = {Cryptology ePrint Archive, Paper 2023/069},
      year = {2023},
      note = {\url{https://eprint.iacr.org/2023/069}},
      url = {https://eprint.iacr.org/2023/069}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.