Quantum commitments from complexity assumptions
From MaRDI portal
Abstract: Bit commitment schemes are at the basis of modern cryptography. Since information-theoretic security is impossible both in the classical and the quantum regime, we need to look at computationally secure commitment schemes. In this paper, we study worst-case complexity assumptions that imply quantum bit-commitment schemes. First, we show that QSZK not included in QMA implies a computationally hiding and statistically binding auxiliary-input quantum commitment scheme. Additionally, we give auxiliary-input commitment schemes using quantum advice that depend on the much weaker assumption that QIP is not included in QMA (which is weaker than PSPACE not included in PP). Finally, we find a quantum oracle relative to which honest-verifier QSZK is not contained in QCMA, the class of languages that can be verified using a classical proof in quantum polynomial time.
Recommendations
- Quantum commitments from complexity assumptions
- Computationally binding quantum commitments
- scientific article; zbMATH DE number 1302858
- Quantum computationally predicate-binding commitments with application in quantum zero-knowledge arguments for NP
- Quantum bit commitment with application in quantum zero-knowledge proof (extended abstract)
Cites work
- \(\mathrm{QIP} = \mathrm{PSPACE}\)
- A Pseudorandom Generator from any One-way Function
- An Unconditional Study of Computational Zero Knowledge
- Bit commitment using pseudorandomness
- Completely Bounded Maps between C∗ -Algebras
- Computing stabilized norms for quantum operations via the theory of completely bounded maps
- Cryptographic distinguishability measures for quantum-mechanical states
- Derandomizing Arthur-Merlin games using hitting sets
- Fidelity for Mixed Quantum States
- Graph Nonisomorphism Has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses
- scientific article; zbMATH DE number 1722671 (Why is no real title available?)
- scientific article; zbMATH DE number 1776257 (Why is no real title available?)
- scientific article; zbMATH DE number 1849957 (Why is no real title available?)
- scientific article; zbMATH DE number 967931 (Why is no real title available?)
- scientific article; zbMATH DE number 4185024 (Why is no real title available?)
- Impossibility of succinct quantum proofs for collision-freeness
- Parallelization, amplification, and exponential time simulation of quantum interactive proof systems
- Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
- Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems
- PSPACE has constant-round quantum interactive proof systems
- Quantum Arthur-Merlin games
- Quantum computations: algorithms and error correction
- Quantum versus classical proofs and advice
- Statistically hiding commitments and statistical zero-knowledge arguments from any one-way function
- Strengths and Weaknesses of Quantum Computing
Cited in
(12)- A post-quantum UC-commitment scheme in the global random oracle model from code-based assumptions
- Classical binding for quantum commitments
- Collapse-binding quantum commitments without random oracles
- Quantum commitments from complexity assumptions
- Computationally binding quantum commitments
- Quantum commitments and signatures without one-way functions
- General properties of quantum bit commitments (extended abstract)
- Black-box separations for non-interactive classical commitments in a quantum world
- Quantum computationally predicate-binding commitments with application in quantum zero-knowledge arguments for NP
- Unconditionally secure quantum commitments with preprocessing
- Unconditionally secure commitments with quantum auxiliary inputs
- The power of a single Haar random state: constructing and separating quantum pseudorandomness
This page was built for publication: Quantum commitments from complexity assumptions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q260394)
