Uncloneable Quantum Advice
Open Access
- 7 October 2024
- journal article
- Published by International Association for Cryptologic Research in IACR Communications in Cryptology
- Vol. 1 (3)
Abstract
The famous no-cloning principle has been shown recently to enable a number of uncloneable cryptographic primitives, including the copy-protection of certain functionalities. Here we address for the first time unkeyed quantum uncloneablity, via the study of a complexity-theoretic tool that enables a computation, but that is natively unkeyed: quantum advice. Remarkably, this is an application of the no-cloning principle in a context where the quantum states of interest are not chosen by a random process. We establish unconditional constructions for promise problems admitting uncloneable quantum advice and, assuming the feasibility of quantum copy-protecting certain functions, for languages with uncloneable advice. Along the way, we note that state complexity classes, introduced by Rosenthal and Yuen (ITCS 2022) — which concern the computational difficulty of synthesizing sequences of quantum states — can be naturally generalized to obtain state cloning complexity classes. We make initial observations on these classes, notably obtaining a result analogous to the existence of undecidable problems. Our proof technique defines and constructs ingenerable sequences of finite bit strings, essentially meaning that they cannot be generated by any uniform circuit family with non-negligible probability. We then prove a generic result showing that the difficulty of accomplishing a computational task on uniformly random inputs implies its difficulty on any fixed, ingenerable sequence. We use this result to derandomize quantum cryptographic games that relate to cloning, and then incorporate a result of Kundu and Tan (arXiv 2022) to obtain uncloneable advice. Applying this two-step process to a monogamy-of-entanglement game yields a promise problem with uncloneable advice, and applying it to the quantum copy-protection of pseudorandom functions with super-logarithmic output lengths yields a language with uncloneable advice.Keywords
All Related Versions
Funding Information
- United States Air Force Office of Scientific Research (FA9550-20-1-0375)
- Natural Sciences and Engineering Research Council
- University of Ottawa
This publication has 43 references indexed in Scilit:
- Cloning Games: A General Framework for Unclonable Primitives2023
- Secure Software Leasing Without Assumptions2021
- New Approaches for Quantum Copy-Protection2021
- Hidden Cosets and Applications to Unclonable Cryptography2021
- Secure Software Leasing2021
- An Introduction to Kolmogorov Complexity and Its Applications2019
- Quantum Computational Complexity2013
- Optimal Counterfeiting Attacks and Generalizations for Wiesner’s Quantum Money2013
- A Quantum Goldreich-Levin Theorem with Cryptographic Applications2002
- The concept of transition in quantum mechanicsFoundations of Physics, 1970