Quantum garbled circuits

DOI10.1145/3519935.3520073MaRDI QIDQ6083535zbMATH OpenWikidataFDO

Authors Zvika Brakerski, Henry C. Yuen

Publication date 8 December 2023

Published in Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2006.01085

zbMATH Keywords

quantum garbled circuitsquantum randomized encodings

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Abstract: We present a garbling scheme for quantum circuits, thus achieving a decomposable randomized encoding scheme for quantum computation. Specifically, we show how to compute an encoding of a given quantum circuit and quantum input, from which it is possible to derive the output of the computation and nothing else. In the classical setting, garbled circuits (and randomized encodings in general) are a versatile cryptographic tool with many applications such as secure multiparty computation, delegated computation, depth-reduction of cryptographic primitives, complexity lower-bounds, and more. However, a quantum analogue for garbling general circuits was not known prior to this work. We hope that our quantum randomized encoding scheme can similarly be useful for applications in quantum computing and cryptography. To illustrate the usefulness of quantum randomized encoding, we use it to design a conceptually-simple zero-knowledge (ZK) proof system for the complexity class $mathbfQMA$. Our protocol has the so-called $Sigma$ format with a single-bit challenge, and allows the inputs to be delayed to the last round. The only previously-known ZK $Sigma$-protocol for $mathbfQMA$ is due to Broadbent and Grilo (FOCS 2020), which does not have the aforementioned properties.

Cited in

(7)

• scientific article; zbMATH DE number 6866338 (Why is no real title available?)
• On concurrent multi-party quantum computation
• Secure computation with shared EPR pairs (or: how to teleport in zero-knowledge)
• Quantum private function evaluation
• Beyond MPC-in-the-head: black-box constructions of short zero-knowledge proofs
• Pseudorandom strings from pseudorandom quantum states
• Robust combiners and universal constructions for quantum cryptography

This page was built for publication: Quantum garbled circuits

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6083535)