On the Concurrent Composition of Quantum Zero-Knowledge
- URL: http://arxiv.org/abs/2012.03139v4
- Date: Sun, 18 Jul 2021 00:02:03 GMT
- Title: On the Concurrent Composition of Quantum Zero-Knowledge
- Authors: Prabhanjan Ananth, Kai-Min Chung, Rolando L. La Placa
- Abstract summary: We study the notion of zero-knowledge secure against quantum-time verifiers (referred to as quantum zero-knowledge) in the concurrent composition setting.
Our result yields a proof of quantum knowledge system for QMA with better parameters than prior works.
- Score: 11.09538194395154
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the notion of zero-knowledge secure against quantum polynomial-time
verifiers (referred to as quantum zero-knowledge) in the concurrent composition
setting. Despite being extensively studied in the classical setting, concurrent
composition in the quantum setting has hardly been studied. We initiate a
formal study of concurrent quantum zero-knowledge. Our results are as follows:
-Bounded Concurrent QZK for NP and QMA: Assuming post-quantum one-way
functions, there exists a quantum zero-knowledge proof system for NP in the
bounded concurrent setting. In this setting, we fix a priori the number of
verifiers that can simultaneously interact with the prover. Under the same
assumption, we also show that there exists a quantum zero-knowledge proof
system for QMA in the bounded concurrency setting.
-Quantum Proofs of Knowledge: Assuming quantum hardness of learning with
errors (QLWE), there exists a bounded concurrent zero-knowledge proof system
for NP satisfying quantum proof of knowledge property. Our extraction mechanism
simultaneously allows for extraction probability to be negligibly close to
acceptance probability (extractability) and also ensures that the prover's
state after extraction is statistically close to the prover's state after
interacting with the verifier (simulatability). The seminal work of [Unruh
EUROCRYPT'12], and all its followups, satisfied a weaker version of
extractability property and moreover, did not achieve simulatability. Our
result yields a proof of quantum knowledge system for QMA with better
parameters than prior works.
Related papers
- On the Relativistic Zero Knowledge Quantum Proofs of Knowledge [1.660294296252135]
We study relativistic zero-knowledge quantum proof of knowledge systems with classical communication.
We show that there exists quantum proofs of knowledge with knowledge error 1/2 + negl(eta) for all relations in NP.
We develop a new multi-prover quantum rewinding technique by combining ideas from monogamy of entanglement and gentle measurement lemmas.
arXiv Detail & Related papers (2024-09-05T15:50:30Z) - Unconditionally Secure Commitments with Quantum Auxiliary Inputs [8.093227427119325]
We show the following unconditional results on quantum commitments in two related yet different models.
We revisit the notion of quantum auxiliary-input commitments introduced by Chailloux, Kerenidis, and Rosgen (Comput. Complex. 2016)
We introduce a new model which we call the common reference quantum state (CRQS) model where both the committer and receiver take the same quantum state that is randomly sampled by an efficient setup algorithm.
arXiv Detail & Related papers (2023-11-30T13:57:30Z) - Unifying (Quantum) Statistical and Parametrized (Quantum) Algorithms [65.268245109828]
We take inspiration from Kearns' SQ oracle and Valiant's weak evaluation oracle.
We introduce an extensive yet intuitive framework that yields unconditional lower bounds for learning from evaluation queries.
arXiv Detail & Related papers (2023-10-26T18:23:21Z) - Quantum Conformal Prediction for Reliable Uncertainty Quantification in
Quantum Machine Learning [47.991114317813555]
Quantum models implement implicit probabilistic predictors that produce multiple random decisions for each input through measurement shots.
This paper proposes to leverage such randomness to define prediction sets for both classification and regression that provably capture the uncertainty of the model.
arXiv Detail & Related papers (2023-04-06T22:05:21Z) - 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) - Approximation of the Nearest Classical-Classical State to a Quantum
State [0.0]
A revolutionary step in computation is driven by quantumness or quantum correlations, which are permanent in entanglements but often in separable states.
The exact quantification of quantumness is an NP-hard problem; thus, we consider alternative approaches to approximate it.
We show that the objective value decreases along the flow by proofs and numerical results.
arXiv Detail & Related papers (2023-01-23T08:26:17Z) - Commitments to Quantum States [11.217084610985674]
A commitment to quantum messages is binding if, after the commit phase, the committed state is hidden from the sender's view.
We show that hiding quantum state commitments (QSCs) are implied by any commitment scheme for classical messages.
Commitments to quantum states open the door to many new cryptographic possibilities.
arXiv Detail & Related papers (2022-10-11T04:34:36Z) - 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) - On exploring the potential of quantum auto-encoder for learning quantum systems [60.909817434753315]
We devise three effective QAE-based learning protocols to address three classically computational hard learning problems.
Our work sheds new light on developing advanced quantum learning algorithms to accomplish hard quantum physics and quantum information processing tasks.
arXiv Detail & Related papers (2021-06-29T14:01:40Z) - A Black-Box Approach to Post-Quantum Zero-Knowledge in Constant Rounds [12.525959293825318]
We construct a constant round interactive proof for NP that satisfies statistical soundness and black-box $epsilon$-zero-knowledge against quantum attacks.
At the heart of our results is a new quantum rewinding technique that enables a simulator to extract a committed message of a malicious verifier.
arXiv Detail & Related papers (2020-11-05T05:40:05Z) - 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)
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.