Uncloneable Quantum Advice

Anne Broadbent; Martti Karvonen; Sébastien Lord

doi:10.62056/abe0fhbmo

Uncloneable Quantum Advice

Authors

Anne Broadbent, Martti Karvonen, Sébastien Lord

Anne Broadbent

University of Ottawa, Ottawa, Canada
anne dot broadbent at uottawa dot ca

Martti Karvonen

University College London, London, United Kingdom
martti dot karvonen at ucl dot ac dot uk

Sébastien Lord

University of Ottawa, Ottawa, Canada
sebastien dot lord at uottawa dot ca

Keywords: Quantum Advice Copy-Protection Ingenerable Sequences

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.

References

[Aar05]

Scott Aaronson. Limitations of quantum advice and one-way communication. Theory of Computing, 1(1):1–28, 2005. DOI: 10.4086/toc.2005.v001a001

Google Scholar ePrint

[Aar09]

Scott Aaronson. Quantum Copy-Protection and Quantum Money. In 24th Annual Conference on Computational Complexity (CCC 2009), pages 229-242. 2009. DOI: 10.1109/CCC.2009.42

Google Scholar ePrint

[AB09]

Sanjeev Arora and Boaz Barak. Computational Complexity: A Modern Approach. Cambridge University Press 2009.

Google Scholar ePrint

[AC02]

Mark Adcock and Richard Cleve. A Quantum Goldreich-Levin Theorem with Cryptographic Applications. In 19th Annual Symposium on Theoretical Aspects of Computer Science — STACS 2002, pages 323–334. 2002. DOI: 10.1007/3-540-45841-7_26

Google Scholar ePrint

[AKL23]

Prabhanjan Ananth, Fatih Kaleoglu, and Qipeng Liu. Cloning Games: A General Framework for Unclonable Primitives. In Advances in Cryptology – CRYPTO 2023, volume 5, pages 66–98. 2023. DOI: 10.1007/978-3-031-38554-4_3

Google Scholar ePrint

[ALL⁺21]

Scott Aaronson, Jiahui Liu, Qipeng Liu, Mark Zhandry, and Ruizhe Zhang. New Approaches for Quantum Copy-Protection. In Advances in Cryptology – CRYPTO 2021, volume 1, pages 526–555. 2021. DOI: 10.1007/978-3-030-84242-0_19

Google Scholar ePrint

[ALP21]

Prabhanjan Ananth and Rolando L. La Placa. Secure Software Leasing. In Advances in Cryptology — EUROCRYPT 2021, volume 2, pages 501–530. 2021. DOI: 10.1007/978-3-030-77886-6_17

Google Scholar ePrint

[BB84]

Charles H. Bennett and Gilles Brassard. Quantum cryptography: Public key distribution and coin tossing. In International Conference on Computers, Systems and Signal Processing, pages 175–179. 1984.

Google Scholar ePrint

[BDE⁺98]

Dagmar Bruß, David P. DiVincenzo, Artur Ekert, Christopher A. Fuchs, Chiara Macchiavello, and John A. Smolin. Optimal universal and state-dependent quantum cloning. Physical Review A, 57(4):2368, 1998. DOI: 10.1103/PhysRevA.57.2368

Google Scholar ePrint

[Bel02]

Mihir Bellare. A Note on Negligible Functions. Journal of Cryptology, 15(4):271–284, 2002. DOI: 10.1007/s00145-002-0116-x

Google Scholar ePrint

[BGT21]

Adam Bouland and Tudor Giurgică-Tiron. Efficient Universal Quantum Compilation: An Inverse-free Solovay-Kitaev Algorithm. Eprint arXiv:2112.02040v1 [quant-ph]. 2021.

Google Scholar ePrint

[BH96]

Vladimir Bužek and Mark Hillery. Quantum copying: Beyond the no-cloning theorem. Physical Review A, 54(3):1844–1852, 1996. DOI: 10.1103/PhysRevA.54.1844

Google Scholar ePrint

[BJL⁺21]

Anne Broadbent, Stacey Jeffery, Sébastien Lord, Supartha Podder, and Aarthi Sundaram. Secure Software Leasing Without Assumptions. In Theory of Cryptography (TCC 2021), volume 1, pages 90–120. 2021. DOI: 10.1007/978-3-030-90459-3_4

Google Scholar ePrint

[BL20]

Anne Broadbent and Sébastien Lord. Uncloneable Quantum Encryption via Oracles. In 15th Conference on the Theory of Quantum Computation, Communication, and Cryptography (TQC 2020), pages 4:1–4:22. 2020. DOI: 10.4230/LIPIcs.TQC.2020.4

Google Scholar ePrint

[Bra85]

Gilles Brassard. Crusade for a better notation. ACM SIGACT News, 17(1):60–64, 1985. DOI: 10.1145/382250.382808

Google Scholar ePrint

[BV97]

Ethan Bernstein and Umesh Vazirani. Quantum Complexity Theory. SIAM Journal on Computing, 26(5):1411–1473, 1997. DOI: 10.1137/S0097539796300921

Google Scholar ePrint

[CLLZ21]

Andrea Coladangelo, Jiahui Liu, Qipeng Liu, and Mark Zhandry. Hidden Cosets and Applications to Unclonable Cryptography. In Advances in Cryptology — CRYPTO 2021, volume 1, pages 556–584. 2021. DOI: 10.1007/978-3-030-84242-0_20

Google Scholar ePrint

[CMP24]

Andrea Coladangelo, Christian Majenz, and Alexander Poremba. Quantum copy-protection of compute-and-compare programs in the quantum random oracle model. Quantum, 8:1330, 2024. DOI: 10.22331/q-2024-05-02-1330

Google Scholar ePrint

[Die82]

Dennis Dieks. Communication by EPR devices. Physics Letters A, 92(6):271–272, 1982. DOI: 10.1016/0375-9601(82)90084-6

Google Scholar ePrint

[DN06]

Christopher M. Dawson and Micheal A. Nielsen. The Solovay-Kitaev algorithm. Quantum Information & Computation, 6(1):81–95, 2006. DOI: 10.26421/QIC6.1-6

Google Scholar ePrint

[EPR35]

A. Einstein, B. Podolsky, and N. Rosen. Can Quantum-Mechanical Description of Physical Reality Be Considered Complete?. Physical Review Letters, 47(10):777-780, 1935. DOI: 10.1103/physrev.47.777

Google Scholar ePrint

[Got03]

Daniel Gottesman. Uncloneable Encryption. Quantum Information & Computation, 3(6):581–602, 2003. DOI: 10.26421/QIC3.6-2

Google Scholar ePrint

[Her82]

Nick Herbert. FLASH — A superluminal communicator based upon a new kind of quantum measurement. Foundations of Physics, 12(12):1171–1179, 1982. DOI: 10.1007/BF00729622

Google Scholar ePrint

[JJUW11]

Rahul Jain, Zhengfeng Ji, Sarvagya Upadhyay, and John Watrous. QIP = PSPACE. Journal of the ACM, 58(6):30, 2011. DOI: 10.1145/2049697.2049704

Google Scholar ePrint

[Kit97]

A. Yu. Kitaev. Quantum computations: algorithms and error correction. Russian Mathematical Surveys, 52(6):1191–1249, 1997. DOI: 10.1070/RM1997v052n06ABEH002155

Google Scholar ePrint

[Knu76]

Donald E. Knuth. Big Omicron and big Omega and big Theta. ACM SIGACT News, 8(2):18–24, 1976. DOI: 10.1145/1008328.1008329

Google Scholar ePrint

[KT22]

Srijita Kundu and Ernest Y.-Z. Tan. Device-independent uncloneable encryption. Eprint arXiv:2207.01058v1 [quant-ph]. 2022.

Google Scholar ePrint

[LFM⁺24]

Mariano Lemus, Ricardo Faleiro, Paulo Mateus, Nikola Paunković, and André Souto. Quantum Kolmogorov complexity and quantum correlations in deterministic-control quantum Turing machines. Quantum, 8:1230, 2024. DOI: 10.22331/q-2024-01-18-1230

Google Scholar ePrint

[LV19]

Ming Li and Paul Vitányi. An Introduction to Kolmogorov Complexity and Its Applications. Springer, Fourth edition. 2019. DOI: 10.1007/978-3-030-11298-1

Google Scholar ePrint

[MVW13]

Abel Molina, Thomas Vidick, and John Watrous. Optimal Counterfeiting Attacks and Generalizations for Wiesner's Quantum Money. In Theory of Quantum Computation, Communication, and Cryptography (TQC 2012), pages 45–64. 2013. DOI: 10.1007/978-3-642-35656-8_4

Google Scholar ePrint

[MW05]

Chris Marriott and John Watrous. Quantum Arthur–Merlin games. Computational Complexity, 14(2):122–152, 2005. DOI: 10.1007/s00037-005-0194-x

Google Scholar ePrint

[MY23]

Tony Metger and Henry Yuen. $\mathsf{stateQIP} = \mathsf{statePSPACE}$. In 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS), pages 1349-1356. 2023. DOI: 10.1109/FOCS57990.2023.00082

Google Scholar ePrint

[NC10]

Michael A. Nielsen and Isaac L. Chuang. Quantum Computation and Quantum Information. Cambridge University Press, 10th Anniversary edition. 2010. DOI: 10.1017/CBO9780511976667

Google Scholar ePrint

[NW06]

Turlough Neary and Damien Woods. Small fast universal Turing machines. Theoretical Computer Science, 362(1):171–195, 2006. DOI: 10.1016/j.tcs.2006.06.002

Google Scholar ePrint

[NY04]

Harumichi Nishimura and Tomoyuki Yamakami. Polynomial time quantum computation with advice. Information Processing Letters, 90(4):195–204, 2004. DOI: 10.1016/j.ipl.2004.02.005

Google Scholar ePrint

[OED22]

Clonable, adj.. Oxford English Dictionary Online. 2022.

Google Scholar ePrint

[Ort18]

Juan Ortigoso. Twelve years before the quantum no-cloning theorem. American Journal of Physics, 86(3):201–205, 2018. DOI: 10.1119/1.5021356

Google Scholar ePrint

[Par70]

James L. Park. The concept of transition in quantum mechanics. Foundations of Physics, 1(1):23–33, 1970. DOI: 10.1007/BF00708652

Google Scholar ePrint

[RY22]

Gregory Rosenthal and Henry Yuen. Interactive Proofs for Synthesizing Quantum States and Unitaries. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022), pages 112:1–112:4. 2022. DOI: 10.4230/LIPIcs.ITCS.2022.112

Google Scholar ePrint

[TFKW13]

Marco Tomamichel, Serge Fehr, Jędrzej Kaniewski, and Stephanie Wehner. A monogamy-of-entanglement game with applications to device-independent quantum cryptography. New Journal of Physics, 15(10):103002, 2013. DOI: 10.1088/1367-2630/15/10/103002

Google Scholar ePrint

[Wat09]

John Watrous. Quantum computational complexity. In Encyclopedia of complexity and systems science, pages 7174–7201. Springer 2009. DOI: 10.1007/978-3-642-27737-5_428-3

Google Scholar ePrint

[Wat18]

John Watrous. The Theory of Quantum Information. Cambridge University Press 2018. DOI: 10.1017/9781316848142

Google Scholar ePrint

[Wer98]

R. F. Werner. Optimal cloning of pure states. Physical Review A, 58(3):1827, 1998. DOI: 10.1103/PhysRevA.58.1827

Google Scholar ePrint

[Wie83]

Stephen Wiesner. Conjugate Coding. ACM SIGACT News, 15(1):78-88, 1983. DOI: 10.1145/1008908.1008920

Google Scholar ePrint

[WZ82]

W. K. Wootters and W. H. Zurek. A single quantum cannot be cloned. Nature, 299:802–803, 1982. DOI: 10.1038/299802a0

Google Scholar ePrint

PDF Open access

DOI: https://doi.org/10.62056/abe0fhbmo

History

Submitted: 2024-07-07
Accepted: 2024-09-02
Published: 2024-10-07

How to cite

Anne Broadbent, Martti Karvonen, and Sébastien Lord, Uncloneable Quantum Advice. IACR Communications in Cryptology, vol. 1, no. 3, Oct 07, 2024, doi: 10.62056/abe0fhbmo.

License

Copyright is held by the author(s)

This work is licensed under a Creative Commons Attribution (CC BY) license.

@article{CiC-1-3-18,
    author = "Broadbent, Anne and Karvonen, Martti and Lord, Sébastien",
    journal = "{IACR} {C}ommunications in {C}ryptology",
    publisher = "{I}nternational {A}ssociation for {C}ryptologic {R}esearch",
    title = "Uncloneable Quantum Advice",
    volume = "1",
    number = "3",
    date = "2024-10-07",
    year = "2024",
    issn = "3006-5496",
    doi = "10.62056/abe0fhbmo"
}

TY - JOUR
AU - Broadbent, Anne
AU - Karvonen, Martti
AU - Lord, Sébastien
PY  - 2024
TI  - Uncloneable Quantum Advice
JF  - IACR Communications in Cryptology
JA  - CIC
VL  - 1
IS  - 3
DO  - 10.62056/abe0fhbmo
UR  - https://doi.org/10.62056/abe0fhbmo
AB  - <p>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.</p><p>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. </p>
ER  -

Anne Broadbent, Martti Karvonen, and Sébastien Lord, Uncloneable Quantum Advice. IACR Communications in Cryptology, vol. 1, no. 3, Oct 07, 2024, doi: 10.62056/abe0fhbmo.