Paper 2023/252

Obfuscation of Pseudo-Deterministic Quantum Circuits

James Bartusek, UC Berkeley
Fuyuki Kitagawa, NTT Social Informatics Laboratories
Ryo Nishimaki, NTT Social Informatics Laboratories
Takashi Yamakawa, NTT Social Informatics Laboratories

We show how to obfuscate pseudo-deterministic quantum circuits in the classical oracle model, assuming the quantum hardness of learning with errors. Given the classical description of a quantum circuit $Q$, our obfuscator outputs a quantum state $\ket{\widetilde{Q}}$ that can be used to evaluate $Q$ repeatedly on arbitrary inputs. Instantiating the classical oracle using any candidate post-quantum indistinguishability obfuscator gives us the first candidate construction of indistinguishability obfuscation for all polynomial-size pseudo-deterministic quantum circuits. In particular, our scheme is the first candidate obfuscator for a class of circuits that is powerful enough to implement Shor's algorithm (SICOMP 1997). Our approach follows Bartusek and Malavolta (ITCS 2022), who obfuscate \emph{null} quantum circuits by obfuscating the verifier of an appropriate classical verification of quantum computation (CVQC) scheme. We go beyond null circuits by constructing a publicly-verifiable CVQC scheme for quantum \emph{partitioning} circuits, which can be used to verify the evaluation procedure of Mahadev's quantum fully-homomorphic encryption scheme (FOCS 2018). We achieve this by upgrading the one-time secure scheme of Bartusek (TCC 2021) to a fully reusable scheme, via a publicly-decodable \emph{Pauli functional commitment}, which we formally define and construct in this work. This commitment scheme, which satisfies a notion of binding against committers that can access the receiver's standard and Hadamard basis decoding functionalities, is constructed by building on techniques of Amos, Georgiou, Kiayias, and Zhandry (STOC 2020) introduced in the context of equivocal but collision-resistant hash functions.

Available format(s)
Publication info
Published elsewhere. Minor revision. STOC 2023
Contact author(s)
bartusek james @ gmail com
fuyuki kitagawa yh @ hco ntt co jp
ryo nishimaki zk @ hco ntt co jp
takashi yamakawa ga @ hco ntt co jp
2023-11-19: last of 2 revisions
2023-02-22: received
See all versions
Short URL
No rights reserved


      author = {James Bartusek and Fuyuki Kitagawa and Ryo Nishimaki and Takashi Yamakawa},
      title = {Obfuscation of Pseudo-Deterministic Quantum Circuits},
      howpublished = {Cryptology ePrint Archive, Paper 2023/252},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.