Publicly verifiable quantum money from random lattices
- URL: http://arxiv.org/abs/2207.13135v3
- Date: Tue, 30 Aug 2022 22:19:52 GMT
- Title: Publicly verifiable quantum money from random lattices
- Authors: Andrey Boris Khesin, Jonathan Z. Lu, Peter W. Shor
- Abstract summary: We develop a cryptographic scheme for publicly verifiable quantum money based on Gaussian superpositions over random lattices.
We prove the unforgeability of our quantum money under the hardness of the short vector problem from lattice-based cryptography.
- Score: 2.2559617939136505
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Publicly verifiable quantum money is a protocol for the preparation of
quantum states that can be efficiently verified by any party for authenticity
but is computationally infeasible to counterfeit. We develop a cryptographic
scheme for publicly verifiable quantum money based on Gaussian superpositions
over random lattices. We introduce a verification-of-authenticity procedure
based on the lattice discrete Fourier transform, and subsequently prove the
unforgeability of our quantum money under the hardness of the short vector
problem from lattice-based cryptography.
Related papers
- Classical certification of quantum gates under the dimension assumption [0.1874930567916036]
We develop an efficient method for certifying single-qubit quantum gates in a black-box scenario.
We prove that the method's sample complexity grows as $mathrmO(varepsilon-1)$.
We show that the proposed method can be used to certify a gate set universal for single-qubit quantum computation.
arXiv Detail & Related papers (2024-01-30T13:40:39Z) - A Cryptographic Perspective on the Verifiability of Quantum Advantage [5.857929080874288]
This paper investigates the verification of quantum advantage from a cryptographic perspective.
We establish a strong connection between the verifiability of quantum advantage and cryptographic and complexity primitives.
Our work shows that the quest for verifiable quantum advantages may lead to applications of quantum cryptography.
arXiv Detail & Related papers (2023-10-23T00:31:51Z) - 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) - On the (Im)plausibility of Public-Key Quantum Money from
Collision-Resistant Hash Functions [6.164147034988822]
We present the first black-box separation of quantum money and cryptographic primitives.
Specifically, we show that collision-resistant hash functions cannot be used as a black-box to construct public-key quantum money schemes.
arXiv Detail & Related papers (2023-01-23T00:44:54Z) - Another Round of Breaking and Making Quantum Money: How to Not Build It
from Lattices, and More [13.02553999059921]
We provide both negative and positive results for publicly verifiable quantum money.
We propose a framework for building quantum money and quantum lightning.
We discuss potential instantiations of our framework.
arXiv Detail & Related papers (2022-11-22T04:17:32Z) - Qafny: A Quantum-Program Verifier [39.47005122712576]
We present Qafny, an automated proof system for verifying quantum programs.
At its core, Qafny uses a type-guided quantum proof system that translates quantum operations to classical array operations.
We show how Qafny can efficiently verify important quantum algorithms, including quantum-walk algorithms, Grover's algorithm, and Shor's algorithm.
arXiv Detail & Related papers (2022-11-11T18:50:52Z) - Efficient Bipartite Entanglement Detection Scheme with a Quantum
Adversarial Solver [89.80359585967642]
Proposal reformulates the bipartite entanglement detection as a two-player zero-sum game completed by parameterized quantum circuits.
We experimentally implement our protocol on a linear optical network and exhibit its effectiveness to accomplish the bipartite entanglement detection for 5-qubit quantum pure states and 2-qubit quantum mixed states.
arXiv Detail & Related papers (2022-03-15T09:46:45Z) - Quantum Proofs of Deletion for Learning with Errors [91.3755431537592]
We construct the first fully homomorphic encryption scheme with certified deletion.
Our main technical ingredient is an interactive protocol by which a quantum prover can convince a classical verifier that a sample from the Learning with Errors distribution in the form of a quantum state was deleted.
arXiv Detail & Related papers (2022-03-03T10:07:32Z) - 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) - Post-Quantum Succinct Arguments: Breaking the Quantum Rewinding Barrier [73.70426431502803]
We prove that Kilian's four-message succinct argument system is post-quantum secure in the standard model.
This yields the first post-quantum succinct argument system from any falsifiable assumption.
arXiv Detail & Related papers (2021-03-15T05:09:17Z) - Using Quantum Metrological Bounds in Quantum Error Correction: A Simple
Proof of the Approximate Eastin-Knill Theorem [77.34726150561087]
We present a proof of the approximate Eastin-Knill theorem, which connects the quality of a quantum error-correcting code with its ability to achieve a universal set of logical gates.
Our derivation employs powerful bounds on the quantum Fisher information in generic quantum metrological protocols.
arXiv Detail & Related papers (2020-04-24T17:58:10Z)
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.