Quantum State Obfuscation from Classical Oracles
STOC ’24, June 24–28, 2024, Vancouver, BC, Canada
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
ACM|Proceedings of the 56th Annual ACM Symposium on Theory of Computing
2024
|
| Online Access: | https://hdl.handle.net/1721.1/155718 |
| _version_ | 1824458385825726464 |
|---|---|
| author | Bartusek, James Brakerski, Zvika Vaikuntanathan, Vinod |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Bartusek, James Brakerski, Zvika Vaikuntanathan, Vinod |
| author_sort | Bartusek, James |
| collection | MIT |
| description | STOC ’24, June 24–28, 2024, Vancouver, BC, Canada |
| first_indexed | 2024-09-23T15:50:22Z |
| format | Article |
| id | mit-1721.1/155718 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2025-02-19T04:25:03Z |
| publishDate | 2024 |
| publisher | ACM|Proceedings of the 56th Annual ACM Symposium on Theory of Computing |
| record_format | dspace |
| spelling | mit-1721.1/1557182025-01-02T04:26:44Z Quantum State Obfuscation from Classical Oracles Bartusek, James Brakerski, Zvika Vaikuntanathan, Vinod Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory STOC ’24, June 24–28, 2024, Vancouver, BC, Canada A major unresolved question in quantum cryptography is whether it is possible to obfuscate arbitrary quantum computation. Indeed, there is much yet to understand about the feasibility of quantum obfuscation even in the classical oracle model, where one is given for free the ability to obfuscate any classical circuit. In this work, we develop a new array of techniques that we use to construct a quantum state obfuscator, a powerful notion formalized recently by Coladangelo and Gunn (arXiv:2311.07794) in their pursuit of better software copy-protection schemes. Quantum state obfuscation refers to the task of compiling a quantum program, consisting of a quantum circuit C with a classical description and an auxiliary quantum state ψ, into a functionally-equivalent obfuscated quantum program that hides as much as possible about C and ψ. We prove the security of our obfuscator when applied to any pseudo-deterministic quantum program, i.e. one that computes a (nearly) deterministic classical input / classical output functionality. Our security proof is with respect to an efficient classical oracle, which may be heuristically instantiated using quantum-secure indistinguishability obfuscation for classical circuits. Our result improves upon the recent work of Bartusek, Kitagawa, Nishimaki and Yamakawa (STOC 2023) who also showed how to obfuscate pseudo-deterministic quantum circuits in the classical oracle model, but only ones with a completely classical description. Furthermore, our result answers a question of Coladangelo and Gunn, who provide a construction of quantum state indistinguishability obfuscation with respect to a quantum oracle, but leave the existence of a concrete real-world candidate as an open problem. Indeed, our quantum state obfuscator together with Coladangelo-Gunn gives the first candidate realization of a “best-possible” copy-protection scheme for all polynomial-time functionalities. Our techniques deviate significantly from previous works on quantum obfuscation. We develop several novel technical tools which we expect to be broadly useful in quantum cryptography. These tools include a publicly-verifiable, linearly-homomorphic quantum authentication scheme with classically-decodable ZX measurements (which we build from coset states), and a method for compiling any quantum circuit into a ”linear + measurement” () quantum program: an alternating sequence of CNOT operations and partial ZX measurements. 2024-07-19T15:03:16Z 2024-07-19T15:03:16Z 2024-06-10 2024-07-01T07:48:48Z Article http://purl.org/eprint/type/ConferencePaper 979-8-4007-0383-6 https://hdl.handle.net/1721.1/155718 Bartusek, James, Brakerski, Zvika and Vaikuntanathan, Vinod. 2024. "Quantum State Obfuscation from Classical Oracles." PUBLISHER_POLICY en 10.1145/3618260.3649673 Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. The author(s) application/pdf ACM|Proceedings of the 56th Annual ACM Symposium on Theory of Computing Association for Computing Machinery |
| spellingShingle | Bartusek, James Brakerski, Zvika Vaikuntanathan, Vinod Quantum State Obfuscation from Classical Oracles |
| title | Quantum State Obfuscation from Classical Oracles |
| title_full | Quantum State Obfuscation from Classical Oracles |
| title_fullStr | Quantum State Obfuscation from Classical Oracles |
| title_full_unstemmed | Quantum State Obfuscation from Classical Oracles |
| title_short | Quantum State Obfuscation from Classical Oracles |
| title_sort | quantum state obfuscation from classical oracles |
| url | https://hdl.handle.net/1721.1/155718 |
| work_keys_str_mv | AT bartusekjames quantumstateobfuscationfromclassicaloracles AT brakerskizvika quantumstateobfuscationfromclassicaloracles AT vaikuntanathanvinod quantumstateobfuscationfromclassicaloracles |