Another Round of Breaking and Making Quantum Money: How to Not Build It
from Lattices, and More
- URL: http://arxiv.org/abs/2211.11994v2
- Date: Fri, 30 Dec 2022 19:55:03 GMT
- Title: Another Round of Breaking and Making Quantum Money: How to Not Build It
from Lattices, and More
- Authors: Jiahui Liu, Hart Montgomery, Mark Zhandry
- Abstract summary: 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.
- Score: 13.02553999059921
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Public verification of quantum money has been one of the central objects in
quantum cryptography ever since Wiesner's pioneering idea of using quantum
mechanics to construct banknotes against counterfeiting. So far, we do not know
any publicly-verifiable quantum money scheme that is provably secure from
standard assumptions.
In this work, we provide both negative and positive results for publicly
verifiable quantum money.
**In the first part, we give a general theorem, showing that a certain
natural class of quantum money schemes from lattices cannot be secure. We use
this theorem to break the recent quantum money scheme of Khesin, Lu, and Shor.
**In the second part, we propose a framework for building quantum money and
quantum lightning we call invariant money which abstracts some of the ideas of
quantum money from knots by Farhi et al.(ITCS'12). In addition to formalizing
this framework, we provide concrete hard computational problems loosely
inspired by classical knowledge-of-exponent assumptions, whose hardness would
imply the security of quantum lightning, a strengthening of quantum money where
not even the bank can duplicate banknotes.
**We discuss potential instantiations of our framework, including an oracle
construction using cryptographic group actions and instantiations from
rerandomizable functional encryption, isogenies over elliptic curves, and
knots.
Related papers
- Cloud-based Semi-Quantum Money [8.252999068253603]
In the 1970s, Wiesner introduced the concept of quantum money, where quantum states generated according to specific rules function as currency.
Quantum computers capable of minting and preserving quantum money have not yet emerged.
Existing quantum channels are not stable enough to support the efficient transmission of quantum states for quantum money.
arXiv Detail & Related papers (2024-07-16T07:40:17Z) - Quantum State Obfuscation from Classical Oracles [18.878095837031292]
A major unresolved question in quantum cryptography is whether it is possible to obfuscate arbitrary quantum computation.
We develop a new array of techniques that we use to construct a quantum state obfuscator.
arXiv Detail & Related papers (2024-01-18T18:42: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) - 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) - Franchised Quantum Money [13.772109618082382]
We introduce franchised quantum money, an alternative form of quantum money that is easier to construct.
Franchised quantum money retains the features of a useful quantum money scheme, namely unforgeability and local verification.
In franchised quantum money, every user gets a unique secret verification key, and the scheme is secure against counterfeiting and sabotage.
arXiv Detail & Related papers (2021-10-19T05:00:28Z) - Realization of arbitrary doubly-controlled quantum phase gates [62.997667081978825]
We introduce a high-fidelity gate set inspired by a proposal for near-term quantum advantage in optimization problems.
By orchestrating coherent, multi-level control over three transmon qutrits, we synthesize a family of deterministic, continuous-angle quantum phase gates acting in the natural three-qubit computational basis.
arXiv Detail & Related papers (2021-08-03T17:49:09Z) - 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) - Quantum Multi-Solution Bernoulli Search with Applications to Bitcoin's
Post-Quantum Security [67.06003361150228]
A proof of work (PoW) is an important cryptographic construct enabling a party to convince others that they invested some effort in solving a computational task.
In this work, we examine the hardness of finding such chain of PoWs against quantum strategies.
We prove that the chain of PoWs problem reduces to a problem we call multi-solution Bernoulli search, for which we establish its quantum query complexity.
arXiv Detail & Related papers (2020-12-30T18:03:56Z) - 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) - Almost Public Quantum Coins [0.1813006808606333]
A quantum coins scheme, just like the traditional currency coin scheme, all the money states are exact copies of each other.
A quantum money scheme can be private, i.e., only the bank can verify the money states, or public.
We propose a way to lift any private quantum coin scheme to a scheme that closely resembles a public quantum coin scheme.
arXiv Detail & Related papers (2020-02-27T21:00:57Z)
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.