Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Conference on Innovations in Theoretical Computer Science

Quantum money from knots

Edward Farhi, David Gosset, Avinatan Hassidim, Andrew Lutomirski, Peter W. Shor

Published Jan 8, 2012• 90 citations
Publisher

Abstract

Quantum money is a cryptographic protocol in which a mint can produce a quantum state, no one else can copy the state, and anyone (with a quantum computer) can verify that the state came from the mint. We present a concrete quantum money scheme based on superpositions of diagrams that encode oriented links with the same Alexander polynomial. We expect our scheme to be secure against computationally bounded adversaries.

DOI
10.1145/2090236.2090260

Related papers

Quantum money from knots

Edward Farhi, David Gosset, Avinatan Hassidim +2 more

Quantum money is a cryptographic protocol in which a mint can produce a quantum state, no one else can copy the state, and anyone (with a quantum computer) can verify that the state came from the mint. We present a concrete quantum money scheme based on superpositions of diagrams that encode oriented links with the same Alexander polynomial. We expect our scheme to be secure against computationally bounded adversaries.

arXiv:1004.5127•Apr 28, 2010•2 citations

Breaking and making quantum money: toward a new quantum cryptographic protocol

Andrew Lutomirski, Scott Aaronson, Edward Farhi +4 more

Public-key quantum money is a cryptographic protocol in which a bank can create quantum states which anyone can verify but no one except possibly the bank can clone or forge. There are no secure public-key quantum money schemes in the literature; as we show in this paper, the only previously published scheme [1] is insecure. We introduce a category of quantum money protocols which we call collision-free. For these protocols, even the bank cannot prepare multiple identical-looking pieces of quantum money. We present a blueprint for how such a protocol might work as well as a concrete example which we believe may be insecure.

arXiv:0912.3825•International Conference on Supercomputing•Dec 21, 2009•46 citations

Semi-Quantum Money

Roy Radian, Or Sattath

Private quantum money allows a bank to mint quantum money states that it can later verify, but that no one else can forge. In classically verifiable quantum money -- introduced by Gavinsky (CCC 2012) -- the verification is done via an interactive protocol between the bank and the user, where the communication is classical, and the computational resources required of the bank are classical. In this work, we consider memoryless interactive protocols in which the minting is likewise classical, and construct a private money scheme that achieves these two notions simultaneously (i.e., classical verification and classical minting). We call such a construction a private semi-quantum money scheme, since all the requirements from the bank in terms of computation and communication are classical.

arXiv:1908.08889•ACM Conference on Advances in Financial Technologies (AFT)•Oct 21, 2019•34 citations

An online attack against Wiesner's quantum money

Andrew Lutomirski

Wiesner's quantum money [5] is a simple, information-theoretically secure quantum cryptographic protocol. In his protocol, a mint issues quantum bills and anyone can query the mint to authenticate a bill. If the mint returns bogus bills when it is asked to authenticate them, then the protocol can be broken in linear time.

arXiv:1010.0256•Oct 1, 2010•24 citations

Another Round of Breaking and Making Quantum Money: How to Not Build It from Lattices, and More

Jiahui Liu, Hart William Montgomery, Mark Zhandry

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.

arXiv:2211.11994•Nov 22, 2022•2 citations

Quantum Money from Hidden Subspaces

Scott Aaronson, Paul F. Christiano

Forty years ago, Wiesner pointed out that quantum mechanics raises the striking possibility of money that cannot be counterfeited according to the laws of physics. We propose the first quantum money scheme that is (1) public-key, meaning that anyone can verify a banknote as genuine, not only the bank that printed it, and (2) cryptographically secure, under a "classical" hardness assumption that has nothing to do with quantum money. Our scheme is based on hidden subspaces, encoded as the zero-sets of random multivariate polynomials. A main technical advance is to show that the "black-box" version of our scheme, where the polynomials are replaced by classical oracles, is unconditionally secure. Previously, such a result had only been known relative to a quantum oracle (and even there, the proof was never published). Even in Wiesner's original setting -- quantum money that can only be verified by the bank -- we are able to use our techniques to patch a major security hole in Wiesner's scheme. We give the first private-key quantum money scheme that allows unlimited verifications and that remains unconditionally secure, even if the counterfeiter can interact adaptively with the bank. Our money scheme is simpler than previous public-key quantum money schemes, including a knot-based scheme of Farhi et al. The verifier needs to perform only two tests, one in the standard basis and one in the Hadamard basis -- matching the original intuition for quantum money, based on the existence of complementary observables. Our security proofs use a new variant of Ambainis's quantum adversary method, and several other tools that might be of independent interest.

arXiv:1203.4740•Electronic colloquium on computational complexity•Mar 21, 2012•49 citations
Quantum money is a cryptographic protocol in which a mint can produce a quantum state, no one else can copy the state, and anyone (with a quantum computer) can verify that the state came from the mint. We present a concrete quantum money scheme based on superpositions of diagrams that encode oriented links with the same Alexander polynomial. We expect our scheme to be secure against computationally bounded adversaries.
Public-key quantum money is a cryptographic protocol in which a bank can create quantum states which anyone can verify but no one except possibly the bank can clone or forge. There are no secure public-key quantum money schemes in the literature; as we show in this paper, the only previously published scheme [1] is insecure. We introduce a category of quantum money protocols which we call collision-free. For these protocols, even the bank cannot prepare multiple identical-looking pieces of quantum money. We present a blueprint for how such a protocol might work as well as a concrete example which we believe may be insecure.
Private quantum money allows a bank to mint quantum money states that it can later verify, but that no one else can forge. In classically verifiable quantum money -- introduced by Gavinsky (CCC 2012) -- the verification is done via an interactive protocol between the bank and the user, where the communication is classical, and the computational resources required of the bank are classical. In this work, we consider memoryless interactive protocols in which the minting is likewise classical, and construct a private money scheme that achieves these two notions simultaneously (i.e., classical verification and classical minting). We call such a construction a private semi-quantum money scheme, since all the requirements from the bank in terms of computation and communication are classical.
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.
Forty years ago, Wiesner pointed out that quantum mechanics raises the striking possibility of money that cannot be counterfeited according to the laws of physics. We propose the first quantum money scheme that is (1) public-key, meaning that anyone can verify a banknote as genuine, not only the bank that printed it, and (2) cryptographically secure, under a "classical" hardness assumption that has nothing to do with quantum money. Our scheme is based on hidden subspaces, encoded as the zero-sets of random multivariate polynomials. A main technical advance is to show that the "black-box" version of our scheme, where the polynomials are replaced by classical oracles, is unconditionally secure. Previously, such a result had only been known relative to a quantum oracle (and even there, the proof was never published). Even in Wiesner's original setting -- quantum money that can only be verified by the bank -- we are able to use our techniques to patch a major security hole in Wiesner's scheme. We give the first private-key quantum money scheme that allows unlimited verifications and that remains unconditionally secure, even if the counterfeiter can interact adaptively with the bank. Our money scheme is simpler than previous public-key quantum money schemes, including a knot-based scheme of Farhi et al. The verifier needs to perform only two tests, one in the standard basis and one in the Hadamard basis -- matching the original intuition for quantum money, based on the existence of complementary observables. Our security proofs use a new variant of Ambainis's quantum adversary method, and several other tools that might be of independent interest.