Secure Computation with Shared EPR Pairs (Or: How to Teleport in Zero-Knowledge)
share
Can a sender non-interactively transmit one of two strings to a receiver without knowing which string was received? Does there exist minimally-interactive secure multiparty computation that only makes (black-box) use of symmetric-key primitives? We provide affirmative answers to these questions in a model where parties have access to shared EPR pairs, thus demonstrating the cryptographic power of this resource. First, we construct a one-shot (i.e., single message) string oblivious transfer (OT) protocol with random receiver bit in the shared EPR pairs model, assuming the (sub-exponential) hardness of LWE. Building on this, we show that secure teleportation through quantum channels is possible. Specifically, given the description of any quantum operation Q, a sender with (quantum) input ρ can send a single classical message that securely transmits Q(ρ) to a receiver. That is, we realize an ideal quantum channel that takes input ρ from the sender and provably delivers Q(ρ) to the receiver without revealing any other information. This immediately gives a number of applications in the shared EPR pairs model: (1) non-interactive secure computation of unidirectional classical randomized functionalities, (2) NIZK for QMA from standard (sub-exponential) hardness assumptions, and (3) a non-interactive zero-knowledge state synthesis protocol. Next, we construct a two-round (round-optimal) secure multiparty computation protocol for classical functionalities in the shared EPR pairs model that is unconditionally-secure in the (quantum-accessible) random oracle model.
READ FULL TEXT