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) $\Sigma$-protocol for the complexity class QMA. Our protocol has a single-bit challenge, and allows the inputs to be delayed to the last round. The only previously-known ZK $\Sigma$-protocol for QMA is due to Broadbent and Grilo (FOCS 2020), which does not have the aforementioned properties.
Category / Keywords: foundations / Randomized Encoding, Garbled Circuits, Quantum Computing, Zero-Knowledge Date: received 10 Nov 2020 Contact author: zvika brakerski at weizmann ac il Available format(s): PDF | BibTeX Citation Version: 20201110:134142 (All versions of this report) Short URL: ia.cr/2020/1401