Paper 2023/564

Secure Computation with Shared EPR Pairs (Or: How to Teleport in Zero-Knowledge)

James Bartusek, University of California, Berkeley
Dakshita Khurana, University of Illinois Urbana-Champaign
Akshayaram Srinivasan, Tata Institute of Fundamental Research

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 {\em secure teleportation through quantum channels} is possible. Specifically, given the description of any quantum operation $Q$, a sender with (quantum) input $\rho$ can send a single classical message that securely transmits $Q(\rho)$ to a receiver. That is, we realize an ideal quantum channel that takes input $\rho$ from the sender and provably delivers $Q(\rho)$ 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 \emph{classical} randomized functionalities, (2) NIZK for QMA from standard (sub-exponential) hardness assumptions, and (3) a non-interactive \emph{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 \emph{unconditionally-secure} in the (quantum-accessible) random oracle model. Classically, both of these results cannot be obtained without some form of correlated randomness shared between the parties, and the only known approach is to have a trusted dealer set up random (string) OT correlations. In the quantum world, we show that shared EPR pairs (which are simple and can be deterministically generated) are sufficient. At the heart of our work are novel techniques for making use of entangling operations to generate string OT correlations, and for instantiating the Fiat-Shamir transform using correlation-intractability in the quantum setting.

Available format(s)
Cryptographic protocols
Publication info
Quantum oblivious transferCorrelation-intractabilityTwo-round MPC
Contact author(s)
bartusek james @ gmail com
dakshita @ illinois edu
akshayaram srinivasan @ tifr res in
2023-04-24: approved
2023-04-20: received
See all versions
Short URL
No rights reserved


      author = {James Bartusek and Dakshita Khurana and Akshayaram Srinivasan},
      title = {Secure Computation with Shared {EPR} Pairs (Or: How to Teleport in Zero-Knowledge)},
      howpublished = {Cryptology ePrint Archive, Paper 2023/564},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.