A Caltech Library Service

Computationally-Secure and Composable Remote State Preparation

Gheorghiu, Alexandru and Vidick, Thomas (2019) Computationally-Secure and Composable Remote State Preparation. In: 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS). IEEE , Piscataway, NJ, pp. 1024-1033. ISBN 9781728149523.

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


We introduce a protocol between a classical polynomial-time verifier and a quantum polynomial-time prover that allows the verifier to securely delegate to the prover the preparation of certain single-qubit quantum states The prover is unaware of which state he received and moreover, the verifier can check with high confidence whether the preparation was successful. The delegated preparation of single-qubit states is an elementary building block in many quantum cryptographic protocols. We expect our implementation of "random remote state preparation with verification", a functionality first defined in (Dunjko and Kashefi 2014), to be useful for removing the need for quantum communication in such protocols while keeping functionality. The main application that we detail is to a protocol for blind and verifiable delegated quantum computation (DQC) that builds on the work of (Fitzsimons and Kashefi 2018), who provided such a protocol with quantum communication. Recently, both blind an verifiable DQC were shown to be possible, under computational assumptions, with a classical polynomial-time client (Mahadev 2017, Mahadev 2018). Compared to the work of Mahadev, our protocol is more modular, applies to the measurement-based model of computation (instead of the Hamiltonian model) and is composable. Our proof of security builds on ideas introduced in (Brakerski et al. 2018).

Item Type:Book Section
Related URLs:
URLURL TypeDescription Paper
Gheorghiu, Alexandru0000-0001-6225-7168
Vidick, Thomas0000-0002-6405-365X
Additional Information:© 2019 IEEE. We thank Rotem Arnon-Friedman, Vedran Dunjko, Urmila Mahadev and Christopher Portmann for useful discussions. Alexandru Gheorghiu and Thomas Vidick are supported by MURI Grant FA9550-18-1-0161 and the IQIM, an NSF Physics Frontiers Center (NSF Grant PHY-1125565) with support of the Gordon and Betty Moore Foundation (GBMF-12500028). Thomas Vidick is also supported by NSF CAREER Grant CCF-1553477, AFOSR YIP award number FA9550-16-1-0495, and a CIFAR Azrieli Global Scholar award.
Group:Institute for Quantum Information and Matter
Funding AgencyGrant Number
Air Force Office of Scientific Research (AFOSR)FA9550-18-1-0161
Institute for Quantum Information and Matter (IQIM)UNSPECIFIED
Gordon and Betty Moore FoundationGBMF-12500028
Air Force Office of Scientific Research (AFOSR)FA9550-16-1-0495
Canadian Institute for Advanced Research (CIFAR)UNSPECIFIED
Subject Keywords:verifiable quantum computation; composable security; learning with errors
Record Number:CaltechAUTHORS:20200109-143243905
Persistent URL:
Official Citation:A. Gheorghiu and T. Vidick, "Computationally-Secure and Composable Remote State Preparation," 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), Baltimore, MD, USA, 2019, pp. 1024-1033. doi: 10.1109/FOCS.2019.00066
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:100609
Deposited By: George Porter
Deposited On:10 Jan 2020 16:15
Last Modified:16 Nov 2021 17:55

Repository Staff Only: item control page