Post-Quantum Multi-Party Computation

• URL: http://arxiv.org/abs/2005.12904v2
• Date: Fri, 20 Nov 2020 18:14:38 GMT
• Title: Post-Quantum Multi-Party Computation
• Authors: Amit Agarwal, James Bartusek, Vipul Goyal, Dakshita Khurana, Giulio Malavolta
• Abstract summary: 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.
• Score: 32.75732860329838
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We initiate the study of multi-party computation for classical functionalities (in the plain model) with security against malicious polynomial-time quantum adversaries. We observe that existing techniques readily give a polynomial-round protocol, but our main result is a construction of *constant-round* post-quantum multi-party computation. We assume mildly super-polynomial quantum hardness of learning with errors (LWE), and polynomial quantum hardness of an LWE-based circular security assumption. Along the way, we develop the following cryptographic primitives that may be of independent interest: 1. A spooky encryption scheme for relations computable by quantum circuits, from the quantum hardness of an LWE-based circular security assumption. This yields the first quantum multi-key fully-homomorphic encryption scheme with classical keys. 2. Constant-round zero-knowledge secure against multiple parallel quantum verifiers from spooky encryption for relations computable by quantum circuits. To enable this, we develop a new straight-line non-black-box simulation technique against *parallel* verifiers that does not clone the adversary's state. This forms the heart of our technical contribution and may also be relevant to the classical setting. 3. A constant-round post-quantum non-malleable commitment scheme, from the mildly super-polynomial quantum hardness of LWE.

Related papers

• Founding Quantum Cryptography on Quantum Advantage, or, Towards Cryptography from $\mathsf{\#P}$-Hardness [10.438299411521099]
  Recent separations have raised the tantalizing possibility of building quantum cryptography from sources of hardness that persist even if hierarchy collapses. We show that quantum cryptography can be based on the extremely mild assumption that $mathsfP#P notsubseteq mathsf(io)BQP/qpoly$.
  arXiv  Detail & Related papers  (2024-09-23T17:45:33Z)
• Efficient Learning for Linear Properties of Bounded-Gate Quantum Circuits [63.733312560668274]
  Given a quantum circuit containing d tunable RZ gates and G-d Clifford gates, can a learner perform purely classical inference to efficiently predict its linear properties? We prove that the sample complexity scaling linearly in d is necessary and sufficient to achieve a small prediction error, while the corresponding computational complexity may scale exponentially in d. We devise a kernel-based learning model capable of trading off prediction error and computational complexity, transitioning from exponential to scaling in many practical settings.
  arXiv  Detail & Related papers  (2024-08-22T08:21:28Z)
• Commitments from Quantum One-Wayness [0.0]
  This work studies one-way state generators, a natural quantum relaxation of one-way functions. A fundamental question is whether this type of quantum one-wayness suffices to realize quantum cryptography. We prove that one-way state generators with pure state outputs imply quantum bit commitments and secure multiparty computation.
  arXiv  Detail & Related papers  (2023-10-17T18:48:22Z)
• Simple Tests of Quantumness Also Certify Qubits [69.96668065491183]
  A test of quantumness is a protocol that allows a classical verifier to certify (only) that a prover is not classical. We show that tests of quantumness that follow a certain template, which captures recent proposals such as (Kalai et al., 2022) can in fact do much more. Namely, the same protocols can be used for certifying a qubit, a building-block that stands at the heart of applications such as certifiable randomness and classical delegation of quantum computation.
  arXiv  Detail & Related papers  (2023-03-02T14:18:17Z)
• An Algebraic Quantum Circuit Compression Algorithm for Hamiltonian Simulation [55.41644538483948]
  Current generation noisy intermediate-scale quantum (NISQ) computers are severely limited in chip size and error rates. We derive localized circuit transformations to efficiently compress quantum circuits for simulation of certain spin Hamiltonians known as free fermions. The proposed numerical circuit compression algorithm behaves backward stable and scales cubically in the number of spins enabling circuit synthesis beyond $mathcalO(103)$ spins.
  arXiv  Detail & Related papers  (2021-08-06T19:38:03Z)
• 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)
• Indistinguishability Obfuscation of Null Quantum Circuits and Applications [17.72516323214125]
  We study the notion of indistinguishability obfuscation for null quantum circuits (quantum null-iO) We show how quantum null-iO enables a series of new cryptographic primitives that, prior to our work, were unknown to exist even making assumptions.
  arXiv  Detail & Related papers  (2021-06-11T00:08:14Z)
• Quantum Fully Homomorphic Encryption by Integrating Pauli One-time Pad with Quaternions [4.182969308816531]
  Quantum fully homomorphic encryption (QFHE) allows to evaluate quantum circuits on encrypted data. We present a novel QFHE scheme, which extends Pauli one-time pad encryption by relying on the quaternion of SU(2).
  arXiv  Detail & Related papers  (2020-12-08T04:54:02Z)
• On The Round Complexity of Secure Quantum Computation [17.832774161583036]
  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.
  arXiv  Detail & Related papers  (2020-11-23T05:20:28Z)
• 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)
• Electronic structure with direct diagonalization on a D-Wave quantum annealer [62.997667081978825]
  This work implements the general Quantum Annealer Eigensolver (QAE) algorithm to solve the molecular electronic Hamiltonian eigenvalue-eigenvector problem on a D-Wave 2000Q quantum annealer. We demonstrate the use of D-Wave hardware for obtaining ground and electronically excited states across a variety of small molecular systems.
  arXiv  Detail & Related papers  (2020-09-02T22:46:47Z)

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.