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
Abstract

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.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint.
Keywords
Quantum oblivious transferCorrelation-intractabilityTwo-round MPC
Contact author(s)
bartusek james @ gmail com
dakshita @ illinois edu
akshayaram srinivasan @ tifr res in
History
2023-04-24: approved
2023-04-20: received
See all versions
Short URL
https://ia.cr/2023/564
License
No rights reserved
CC0

BibTeX

@misc{cryptoeprint:2023/564,
      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},
      url = {https://eprint.iacr.org/2023/564}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.