License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITCS.2022.15
URN: urn:nbn:de:0030-drops-156115
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/15611/
Go to the corresponding LIPIcs Volume Portal

Bartusek, James ; Malavolta, Giulio

Indistinguishability Obfuscation of Null Quantum Circuits and Applications

pdf-format:
LIPIcs-ITCS-2022-15.pdf (0.6 MB)

Abstract

We study the notion of indistinguishability obfuscation for null quantum circuits (quantum null-iO). We present a construction assuming:
- The quantum hardness of learning with errors (LWE).
- Post-quantum indistinguishability obfuscation for classical circuits.
- A notion of "dual-mode" classical verification of quantum computation (CVQC). We give evidence that our notion of dual-mode CVQC exists by proposing a scheme that is secure assuming LWE in the quantum random oracle model (QROM).
Then we show how quantum null-iO enables a series of new cryptographic primitives that, prior to our work, were unknown to exist even making heuristic assumptions. Among others, we obtain the first witness encryption scheme for QMA, the first publicly verifiable non-interactive zero-knowledge (NIZK) scheme for QMA, and the first attribute-based encryption (ABE) scheme for BQP.

BibTeX - Entry

@InProceedings{bartusek_et_al:LIPIcs.ITCS.2022.15,
  author =	{Bartusek, James and Malavolta, Giulio},
  title =	{{Indistinguishability Obfuscation of Null Quantum Circuits and Applications}},
  booktitle =	{13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
  pages =	{15:1--15:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-217-4},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{215},
  editor =	{Braverman, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/15611},
  URN =		{urn:nbn:de:0030-drops-156115},
  doi =		{10.4230/LIPIcs.ITCS.2022.15},
  annote =	{Keywords: Obfuscation, Witness Encryption, Classical Verification of Quantum Computation}
}

Keywords: Obfuscation, Witness Encryption, Classical Verification of Quantum Computation
Collection: 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)
Issue Date: 2022
Date of publication: 25.01.2022

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI