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

• Anonymous Public-Key Quantum Money and Quantum Voting [15.80411915665245]
  We develop the formal definitions of privacy for quantum money schemes. We then construct the first public-key quantum money schemes that satisfy these security notions. We show that the no-cloning principle, a result of quantum mechanics, allows us to construct schemes, with security guarantees that are classically impossible.
  arXiv  Detail & Related papers  (2024-11-07T07:21:28Z)
• A General Quantum Duality for Representations of Groups with Applications to Quantum Money, Lightning, and Fire [8.714677279673738]
  We show that manipulating quantum states in one basis is equivalent to extracting values in a complementary basis. We present the first secure quantum lightning construction based on a plausible cryptographic assumption. We show equivalence among four security notions: quantum lightning security, worst-case and average-case cloning security, and security against preparing a canonical state.
  arXiv  Detail & Related papers  (2024-11-01T11:56:11Z)
• 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)
• 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)

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.