Commitments from Quantum One-Wayness
- URL: http://arxiv.org/abs/2310.11526v4
- Date: Mon, 29 Jan 2024 18:47:50 GMT
- Title: Commitments from Quantum One-Wayness
- Authors: Dakshita Khurana (UIUC) and Kabir Tomer (UIUC)
- Abstract summary: 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.
- Score: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: One-way functions are central to classical cryptography. They are both
necessary for the existence of non-trivial classical cryptosystems, and
sufficient to realize meaningful primitives including commitments, pseudorandom
generators and digital signatures. At the same time, a mounting body of
evidence suggests that assumptions even weaker than one-way functions may
suffice for many cryptographic tasks of interest in a quantum world, including
bit commitments and secure multi-party computation. This work studies one-way
state generators [Morimae-Yamakawa, CRYPTO 2022], a natural quantum relaxation
of one-way functions. Given a secret key, a one-way state generator outputs a
hard to invert quantum state. A fundamental question is whether this type of
quantum one-wayness suffices to realize quantum cryptography. We obtain an
affirmative answer to this question, by proving that one-way state generators
with pure state outputs imply quantum bit commitments and secure multiparty
computation. Along the way, we build an intermediate primitive with classical
outputs, which we call a (quantum) one-way puzzle. Our main technical
contribution is a proof that one-way puzzles imply quantum bit commitments.
Related papers
- Public-Key Encryption with Quantum Keys [11.069434965621683]
We study the notion of quantum public-key encryption (qPKE) where keys are allowed to be quantum states.
We show that computational assumptions are necessary to build quantum public-key encryption.
arXiv Detail & Related papers (2023-06-13T11:32:28Z) - 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) - Quantum Cryptography: Quantum Key Distribution, a Non-technical Approach [0.0]
Quantum mechanics provides means to create an inherently secure communication channel that is protected by the laws of physics.
This paper is a non-technical overview of quantum key distribution, a type of cryptography poised to exploit the laws of quantum mechanics directly.
arXiv Detail & Related papers (2022-11-09T15:30:23Z) - One-Wayness in Quantum Cryptography [9.09597656634436]
We study properties of one-way state generators (OWSGs), which are a quantum analogue of one-way functions.
We show that Quantum digital signatures are equivalent to OWSGs.
We introduce an variant of OWSGs, which we call secretly-verifiable and statistically-invertible OWSGs.
arXiv Detail & Related papers (2022-10-07T08:21:21Z) - Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
Bernstein-Vazirani algorithm allows one to determine a bit string encoded into an oracle.
We analyze in detail the quantum resources in the Bernstein-Vazirani algorithm.
We show that in the absence of entanglement, the performance of the algorithm is directly related to the amount of quantum coherence in the initial state.
arXiv Detail & Related papers (2022-05-26T20:32:36Z) - Quantum commitments and signatures without one-way functions [9.767030279324038]
In the classical world, the existence of commitments is equivalent to the existence of one-way functions.
In the quantum setting, commitments are not known to imply one-way functions.
We show that commitments with computational hiding and statistical binding exist if pseudorandom quantum states exist.
arXiv Detail & Related papers (2021-12-13T01:13:31Z) - Certification of quantum states with hidden structure of their
bitstrings [0.0]
We propose a numerically cheap procedure to describe and distinguish quantum states.
We show that it is enough to characterize quantum states with different structure of entanglement.
Our approach can be employed to detect phase transitions of different nature in many-body quantum magnetic systems.
arXiv Detail & Related papers (2021-07-21T06:22:35Z) - 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) - 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 Gram-Schmidt Processes and Their Application to Efficient State
Read-out for Quantum Algorithms [87.04438831673063]
We present an efficient read-out protocol that yields the classical vector form of the generated state.
Our protocol suits the case that the output state lies in the row space of the input matrix.
One of our technical tools is an efficient quantum algorithm for performing the Gram-Schmidt orthonormal procedure.
arXiv Detail & Related papers (2020-04-14T11:05:26Z)
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.