Paper 2023/564
Secure Computation with Shared EPR Pairs (Or: How to Teleport in Zero-Knowledge)
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)
- 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
-
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} }