Contributed Talks 1a: Quantum MPC (Chairs: Omar Fawzi and Carl Miller)

Abstract: In the universal blind quantum computation problem, a client wants to make use of a single quantum server to evaluate $C\ket{0}$ where $C$ is an arbitrary quantum circuit while keeping $C$ secret. The client's goal is to use as few resources as possible. This problem, first raised by Broadbent, Fitzsimons and Kashefi\cite{UBQC}, has become fundamental to the study of quantum cryptography, not only because of its own importance, but also because it provides a testbed for new techniques that were later applied to related problems (for example, quantum computation verification). Previous works on this problem mainly focused on either information-theoretically (IT) secure protocols or techniques based on trapdoor assumptions (public key encryptions).\par In this paper we study how the availability of symmetric-key primitives, modeled by a random oracle, changes the complexity of universal blind quantum computation. We give a new universal blind quantum computation protocol. Similar to previous works on IT-secure protocols (for example, BFK\cite{UBQC}), our protocol has an offline phase and an online phase. In the offline phase the client prepares some quantum gadgets with relatively simple quantum gates and sends them to the server, and in the online phase the client is entirely classical --- it does not even need quantum storage. Crucially, the protocol's offline phase is \emph{succinct}, that is, its complexity is independent of the circuit size. Its complexity is only $poly(\kappa)$ where $poly$ is a fixed polynomial, and can be used to evaluate any circuit (or several circuits) of size up to $subexp(\kappa)$. In contrast, known schemes either require the client to perform quantum computations that scale with the size of the circuit \cite{UBQC}, or require trapdoor assumptions \cite{Mahadev2017}.

Abstract: The cryptographic task of secure multi-party (classical) computation has received a lot of attention in the last decades. Even in the extreme case where a computation is performed be- tween k mutually distrustful players, and security is required even for the single honest player if all other players are colluding adversaries, secure protocols are known. For quantum com- putation, on the other hand, protocols allowing arbitrary dishonest majority have only been proven for k = 2. In this work, we generalize the approach taken by Dupuis, Nielsen and Salvail (CRYPTO 2012) in the two-party setting to devise a secure, efficient protocol for multi- party quantum computation for any number of players k, and prove security against up to k − 1 colluding adversaries. The quantum round complexity of the protocol for computing a quantum circuit of {CNOT, T} depth d is O(k · (d + log n)), where n is the security parameter. To achieve efficiency, we develop a novel public verification protocol for the Clifford authen- tication code, and a testing protocol for magic-state inputs, both using classical multi-party computation.

Abstract: In a recent breakthrough, Mahadev constructed an interactive protocol that enables a purely classical party to delegate any quantum computation to an untrusted quantum prover. In this work, we show that this same task can in fact be performed non-interactively and in zero-knowledge. Our protocols result from a sequence of significant improvements to the original four-message protocol of Mahadev. We begin by making the first message instance-independent and moving it to an offline setup phase. We then establish a parallel repetition theorem for the resulting three-message protocol, with an asymptotically optimal rate. This, in turn, enables an application of the Fiat-Shamir heuristic, eliminating the second message and giving a non-interactive protocol. Finally, we employ classical non-interactive zero-knowledge (NIZK) arguments and classical fully homomorphic encryption (FHE) to give a zero-knowledge variant of this construction. This yields the first purely classical NIZK argument system for QMA, a quantum analogue of NP. We establish the security of our protocols under standard assumptions in quantum-secure cryptography. Specifically, our protocols are secure in the Quantum Random Oracle Model, under the assumption that Learning with Errors is quantumly hard. The NIZK construction also requires circuit-private FHE.