Physics – Quantum Physics
Scientific paper
2011-10-24
Proceedings of IEEE Conference on Computational Complexity, pages 229-242, 2009
Physics
Quantum Physics
14-page conference abstract; full version hasn't appeared and will never appear. Being posted to arXiv mostly for archaeologic
Scientific paper
Forty years ago, Wiesner proposed using quantum states to create money that is physically impossible to counterfeit, something that cannot be done in the classical world. However, Wiesner's scheme required a central bank to verify the money, and the question of whether there can be unclonable quantum money that anyone can verify has remained open since. One can also ask a related question, which seems to be new: can quantum states be used as copy-protected programs, which let the user evaluate some function f, but not create more programs for f? This paper tackles both questions using the arsenal of modern computational complexity. Our main result is that there exist quantum oracles relative to which publicly-verifiable quantum money is possible, and any family of functions that cannot be efficiently learned from its input-output behavior can be quantumly copy-protected. This provides the first formal evidence that these tasks are achievable. The technical core of our result is a "Complexity-Theoretic No-Cloning Theorem," which generalizes both the standard No-Cloning Theorem and the optimality of Grover search, and might be of independent interest. Our security argument also requires explicit constructions of quantum t-designs. Moving beyond the oracle world, we also present an explicit candidate scheme for publicly-verifiable quantum money, based on random stabilizer states; as well as two explicit schemes for copy-protecting the family of point functions. We do not know how to base the security of these schemes on any existing cryptographic assumption. (Note that without an oracle, we can only hope for security under some computational assumption.)
No associations
LandOfFree
Quantum Copy-Protection and Quantum Money does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Quantum Copy-Protection and Quantum Money, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Quantum Copy-Protection and Quantum Money will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-93679