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
- 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) - Quantum Query Lower Bounds for Key Recovery Attacks on the Even-Mansour
Cipher [0.0]
Even-Mansour (EM) cipher is one of the famous constructions for a block cipher.
Kuwakado and Morii demonstrated that a quantum adversary can recover its $n$-bit secret keys only with $O(n)$ nonadaptive quantum queries.
arXiv Detail & Related papers (2023-08-21T02:01:30Z) - 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) - Revocable Cryptography from Learning with Errors [61.470151825577034]
We build on the no-cloning principle of quantum mechanics and design cryptographic schemes with key-revocation capabilities.
We consider schemes where secret keys are represented as quantum states with the guarantee that, once the secret key is successfully revoked from a user, they no longer have the ability to perform the same functionality as before.
arXiv Detail & Related papers (2023-02-28T18:58:11Z) - 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.