Unconditionally Secure Commitments with Quantum Auxiliary Inputs
- URL: http://arxiv.org/abs/2311.18566v2
- Date: Fri, 6 Sep 2024 10:08:01 GMT
- Title: Unconditionally Secure Commitments with Quantum Auxiliary Inputs
- Authors: Tomoyuki Morimae, Barak Nehoran, Takashi Yamakawa,
- Abstract summary: 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.
- Score: 8.093227427119325
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We show the following unconditional results on quantum commitments in two related yet different models: 1. We revisit the notion of quantum auxiliary-input commitments introduced by Chailloux, Kerenidis, and Rosgen (Comput. Complex. 2016) where both the committer and receiver take the same quantum state, which is determined by the security parameter, as quantum auxiliary inputs. We show that computationally-hiding and statistically-binding quantum auxiliary-input commitments exist unconditionally, i.e., without relying on any unproven assumption, while Chailloux et al. assumed a complexity-theoretic assumption, ${\bf QIP}\not\subseteq{\bf QMA}$. On the other hand, we observe that achieving both statistical hiding and statistical binding at the same time is impossible even in the quantum auxiliary-input setting. To the best of our knowledge, this is the first example of unconditionally proving computational security of any form of (classical or quantum) commitments for which statistical security is impossible. As intermediate steps toward our construction, we introduce and unconditionally construct post-quantum sparse pseudorandom distributions and quantum auxiliary-input EFI pairs which may be of independent interest. 2. 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. We unconditionally prove that there exist statistically hiding and statistically binding commitments in the CRQS model, circumventing the impossibility in the plain model. We also discuss their applications to zero-knowledge proofs, oblivious transfers, and multi-party computations.
Related papers
- Quantum delegation with an off-the-shelf device [3.3766484312332303]
We show how to delegate-time quantum computations in the OTS model.
This provides the first relativistic (one-round), two-prover zero-knowledge proof system for QMA.
As a proof approach, we provide a new self-test for n EPR pairs using only constant-sized Pauli measurements.
arXiv Detail & Related papers (2023-04-07T02:43:06Z) - 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) - Schrödinger as a Quantum Programmer: Estimating Entanglement via Steering [3.187381965457262]
We develop a quantum algorithm that tests for and quantifies the separability of a general bipartite state by using the quantum steering effect.
Our findings provide a meaningful connection between steering, entanglement, quantum algorithms, and quantum computational complexity theory.
arXiv Detail & Related papers (2023-03-14T13:55:06Z) - 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) - 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) - Improved Quantum Algorithms for Fidelity Estimation [77.34726150561087]
We develop new and efficient quantum algorithms for fidelity estimation with provable performance guarantees.
Our algorithms use advanced quantum linear algebra techniques, such as the quantum singular value transformation.
We prove that fidelity estimation to any non-trivial constant additive accuracy is hard in general.
arXiv Detail & Related papers (2022-03-30T02:02:16Z) - 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) - Non-equilibrium stationary states of quantum non-Hermitian lattice
models [68.8204255655161]
We show how generic non-Hermitian tight-binding lattice models can be realized in an unconditional, quantum-mechanically consistent manner.
We focus on the quantum steady states of such models for both fermionic and bosonic systems.
arXiv Detail & Related papers (2021-03-02T18:56:44Z) - On the Concurrent Composition of Quantum Zero-Knowledge [11.09538194395154]
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.
arXiv Detail & Related papers (2020-12-05T23:09:29Z) - 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) - Quantum Statistical Complexity Measure as a Signalling of Correlation
Transitions [55.41644538483948]
We introduce a quantum version for the statistical complexity measure, in the context of quantum information theory, and use it as a signalling function of quantum order-disorder transitions.
We apply our measure to two exactly solvable Hamiltonian models, namely: the $1D$-Quantum Ising Model and the Heisenberg XXZ spin-$1/2$ chain.
We also compute this measure for one-qubit and two-qubit reduced states for the considered models, and analyse its behaviour across its quantum phase transitions for finite system sizes as well as in the thermodynamic limit by using Bethe ansatz.
arXiv Detail & Related papers (2020-02-05T00:45:21Z)
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.