On The Round Complexity of Secure Quantum Computation

• URL: http://arxiv.org/abs/2011.11212v3
• Date: Fri, 13 Aug 2021 23:36:04 GMT
• Title: On The Round Complexity of Secure Quantum Computation
• Authors: James Bartusek, Andrea Coladangelo, Dakshita Khurana, Fermi Ma
• Abstract summary: We construct the first constant-round protocols for secure quantum computation in the two-party (2PQC) and multi-party (MPQC) settings with security against malicious adversaries.
• Score: 17.832774161583036
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We construct the first constant-round protocols for secure quantum computation in the two-party (2PQC) and multi-party (MPQC) settings with security against malicious adversaries. Our protocols are in the common random string (CRS) model. - Assuming two-message oblivious transfer (OT), we obtain (i) three-message 2PQC, and (ii) five-round MPQC with only three rounds of online (input-dependent) communication; such OT is known from quantum-hard Learning with Errors (QLWE). - Assuming sub-exponential hardness of QLWE, we obtain (i) three-round 2PQC with two online rounds and (ii) four-round MPQC with two online rounds. - When only one (out of two) parties receives output, we achieve minimal interaction (two messages) from two-message OT; classically, such protocols are known as non-interactive secure computation (NISC), and our result constitutes the first maliciously-secure quantum NISC. Additionally assuming reusable malicious designated-verifier NIZK arguments for NP (MDV-NIZKs), we give the first MDV-NIZK for QMA that only requires one copy of the quantum witness. Finally, we perform a preliminary investigation into two-round secure quantum computation where each party must obtain output. On the negative side, we identify a broad class of simulation strategies that suffice for classical two-round secure computation that are unlikely to work in the quantum setting. Next, as a proof-of-concept, we show that two-round secure quantum computation exists with respect to a quantum oracle.

Related papers

• Extending Quantum Perceptrons: Rydberg Devices, Multi-Class Classification, and Error Tolerance [67.77677387243135]
  Quantum Neuromorphic Computing (QNC) merges quantum computation with neural computation to create scalable, noise-resilient algorithms for quantum machine learning (QML) At the core of QNC is the quantum perceptron (QP), which leverages the analog dynamics of interacting qubits to enable universal quantum computation.
  arXiv  Detail & Related papers  (2024-11-13T23:56:20Z)
• Probabilistic versions of Quantum Private Queries [0.7252027234425332]
  We define two non-deterministic versions of Quantum Private Queries, a protocol addressing the Symmetric-Private Information Retrieval problem. We show that the strongest variant of such scheme is formally equivalent to Quantum Bit Commitment, Quantum Oblivious Transfer and One-Sided Two Party Computation protocols.
  arXiv  Detail & Related papers  (2024-01-11T09:04:13Z)
• Quantum Secure Protocols for Multiparty Computations [2.9561405287476177]
  We present secure multiparty computation (MPC) protocols that can withstand quantum attacks. We first present the design and analysis of an information-theoretic secure oblivious linear evaluation (OLE), namely $sf qOLE$ in the quantum domain. We further utilize $sf qOLE$ as a building block to construct a quantum-safe multiparty private set intersection (MPSI) protocol.
  arXiv  Detail & Related papers  (2023-12-26T19:53:29Z)
• Quantum Imitation Learning [74.15588381240795]
  We propose quantum imitation learning (QIL) with a hope to utilize quantum advantage to speed up IL. We develop two QIL algorithms, quantum behavioural cloning (Q-BC) and quantum generative adversarial imitation learning (Q-GAIL) Experiment results demonstrate that both Q-BC and Q-GAIL can achieve comparable performance compared to classical counterparts.
  arXiv  Detail & Related papers  (2023-04-04T12:47:35Z)
• Oblivious Quantum Computation and Delegated Multiparty Quantum Computation [61.12008553173672]
  We propose a new concept, oblivious computation quantum computation, where secrecy of the input qubits and the program to identify the quantum gates are required. Exploiting quantum teleportation, we propose a two-server protocol for this task. Also, we discuss delegated multiparty quantum computation, in which, several users ask multiparty quantum computation to server(s) only using classical communications.
  arXiv  Detail & Related papers  (2022-11-02T09:01:33Z)
• Efficient Bipartite Entanglement Detection Scheme with a Quantum Adversarial Solver [89.80359585967642]
  Proposal reformulates the bipartite entanglement detection as a two-player zero-sum game completed by parameterized quantum circuits. We experimentally implement our protocol on a linear optical network and exhibit its effectiveness to accomplish the bipartite entanglement detection for 5-qubit quantum pure states and 2-qubit quantum mixed states.
  arXiv  Detail & Related papers  (2022-03-15T09:46:45Z)
• Depth-efficient proofs of quantumness [77.34726150561087]
  A proof of quantumness is a type of challenge-response protocol in which a classical verifier can efficiently certify quantum advantage of an untrusted prover. In this paper, we give two proof of quantumness constructions in which the prover need only perform constant-depth quantum circuits.
  arXiv  Detail & Related papers  (2021-07-05T17:45:41Z)
• Delegating Multi-Party Quantum Computations vs. Dishonest Majority in Two Quantum Rounds [0.0]
  Multi-Party Quantum Computation (MPQC) has attracted a lot of attention as a potential killer-app for quantum networks. We present a composable protocol achieving blindness and verifiability even in the case of a single honest client.
  arXiv  Detail & Related papers  (2021-02-25T15:58:09Z)
• Multiparty Mediated Quantum Secret Sharing Protocol [0.0]
  The proposed MQSS protocol has addressed two common challenges in the existing semi-quantum secret sharing protocols. The security analysis has delivered proof to show that the proposed MQSS protocol can avoid the collective attack, the collusion attack, and the Trojan horse attacks.
  arXiv  Detail & Related papers  (2021-02-13T02:09:16Z)
• Secure Two-Party Quantum Computation Over Classical Channels [63.97763079214294]
  We consider the setting where the two parties (a classical Alice and a quantum Bob) can communicate only via a classical channel. We show that it is in general impossible to realize a two-party quantum functionality with black-box simulation in the case of malicious quantum adversaries. We provide a compiler that takes as input a classical proof of quantum knowledge (PoQK) protocol for a QMA relation R and outputs a zero-knowledge PoQK for R that can be verified by classical parties.
  arXiv  Detail & Related papers  (2020-10-15T17:55:31Z)
• Post-Quantum Multi-Party Computation [32.75732860329838]
  We study multi-party computation for classical functionalities (in the plain model) with security against malicious-time quantum adversaries. We assume superpolynomial quantum hardness of learning with errors (LWE), and quantum hardness of an LWE-based circular security assumption. Along the way, we develop cryptographic primitives that may be of independent interest.
  arXiv  Detail & Related papers  (2020-05-23T00:42:52Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.