Communications of the ACM
Research
Uncloneable Cryptography
Credit: Andrij Borys Associates, Fabio Cammarota
Intractable computational problems are a barrier for algorithm designers. Cryptographers are modern lemonade makers. Their lemons are these intractable problems, which they squeeze into sweet lemonade: secure cryptographic protocols. Why is a lemon even required? Because it lets us assume there is something an adversary cannot do. Intractable problems can give the honest user an advantage: for example, the honest user can multiply two large primes. The honest user knows the prime factors of the resulting number; yet, it is widely believed that a classical adversary cannot (efficiently) find these factors.
Cryptographers have been squeezing this computational intractability lemon since the 1970s. Are there any other lemons on which cryptography could be based? Quantum mechanics has quite a few peculiarities. One notable example is the no-cloning theorem, which states that quantum information cannot be cloned. Uncloneable cryptography—the main focus of this review—uses the no-cloning lemon as its main ingredient. For a broader perspective, see Figure 1 on page 80.
Figure 1. Classical cryptography relies on the computational intractability lemon. Uncloneable cryptography combines the computational intractability lemon, with the no-cloning lemon (as detailed in this article). For the reader's orientation, we mention that uncloneable cryptography is a sub-field of quantum cryptography. Quantum cryptography uses two other no-go phenomena as fresh (hence, the green hue in the illustration) lemons: the act of measuring a state collapses it, and this transformation is irreversible: there is no way to "rewind" this process and return to the pre-measured state. Additionally, non-local games have the property that classical strategies get a "low score" compared to the optimal quantum strategies. This article focuses on uncloneable cryptography, and therefore no rewinding and no cloning are not discussed in detail.
Quantum States and No-Cloning
Suppose you are given a sample from a probability distribution you know nothing about. Can you create another independent sample from that distribution? Clearly, the answer is no. The no-cloning theorem states that quantum information behaves the same way: if you are given an unknown quantum state |Ψ〉, it is impossible to create two identical copies of it. Also, the proofs of these two statements are very similar. The no-cloning result and its simple proof use quantum jargon, which can be safely skipped for those unfamiliar.
The transformation |Ψ〉 → |Ψ〉 ⊗ |Ψ〉 is non-linear, and therefore is not permissible by quantum mechanics.
A qubit—the most basic unit of quantum information—is a linear combination of the "0" and "1" state of a single bit, and therefore is analogous to a bit. Yet, the theorem here shows that this analogy shouldn't be taken too literally: unlike bits, which can be copied, there are aspects in which a qubit resembles a (classical) sample from a distribution, since in both cases one copy is not enough to create two independent copies.
Proof.
By definition,
By summing Eqs. (1) and (2), and assuming that the transformation is linear, we have
which contradicts Eq. (3). □
Note this theorem only shows that it is impossible to create two exact clones of all states given a single copy. There are many no-cloning variants where these restrictions are relaxed. For example, Bruß et al.20 discuss optimal state dependent cloners. Here, the cloner (C) receives one of two predetermined states, |α〉, |β〉 ∈ Cd; The cloner's goal is to have F(C(|α〉), |α〉 ⊗ |α〉) ≥ x and F(C(|β〉), |β〉 ⊗ |β〉) ≥ x for x as large as possible, where F is a quantity called the fidelity which measures how close two given states are. Werner49 discusses an optimal N → M cloner for any M > N: the cloner receives N copies of a Haar random state |Ψ〉 ∈ Cd and outputs M registers which have the highest possible fidelity with |Ψ〉⊗M. Among other things, Werner's result shows that poly(n) copies of a Haar random state on n qubits would yield an exponentially small fidelity when trying to produce (only) one additional clone.
Quantum Money and Uncloneable Signatures
The first uncloneable primitive, and arguably the first work in quantum cryptography, was Wiesner's private quantum money scheme.50,a Wiesner's motivation was to design "money that it is physically impossible to counterfeit." His construction is as follows: Upon minting, the bank creates a banknote using n qubits, where each qubit can be in one of the four states 
. The banknote also contains a serial number. For example, the 9th banknote could be ((|1〉 ⊗ | − 〉 ⊗ | + 〉 ⊗ | − 〉 ⊗ |0〉, 9)) (here n = 5, which is too small in practice). The bank also maintains a database, containing a classical description of the quantum state for each of the serial numbers. Money can be verified in each of the bank branches: each bank branch needs to have a copy of the database mentioned here. To verify the 9th banknote in the previous example, the bank would measure the first qubit of the proclaimed state in the 0/1 basis, and reject if the outcome is not 1 (recall that the first qubit is supposed to be |1〉, and therefore measuring it in the standard basis should return 1). Otherwise, it will verify the second qubit by measuring it in the +/- basis, and rejecting if the outcome is not -. This is repeated for all the n qubits.
There are variations of this scheme that are noise-tolerant (that is, money passes verification even if some constant fraction of the qubits are disturbed arbitrarily). A complete analysis proving the security of Wiesner's scheme appeared approximately 40 years later.37,41
Since its inception, quantum money has been improved across multiple dimensions and properties, which are discussed here. Table 1 contains a cell for every combination of these properties. Every such cell contains representative constructions and the common term used for that set of properties, which might not be so obvious: for example, a particular type of keyless quantum money is called quantum lightning. Note that in some cases, one notion is stronger than another. For example, public quantum money is stronger than private quantum money.b In many cases, a construction for some stronger variant is known, while a construction that achieves only the weaker one is not known. We emphasize that one could try to achieve the weaker variant, while improving upon the properties which do not appear in the table, such as, weakening the underlying assumptions, removing the need for an oracle, making the scheme noise-tolerant, improving the efficiency, among others.
Table 1. Variants of quantum money and uncloneable signatures. The letter q. abbreviates quantum.
Types of verification keys. Wiesner's money is reminiscent of credit cards, where a trusted party is involved in any transaction. This type of quantum money is called private since the bank's private key is needed to verify the money. There are three other types of verification keys, shown in the vertical axis in the table, which are discussed next.
Public quantum money, also known as locally verifiable quantum money, resembles cash: verification can be done without the bank, using the bank's public key. No public quantum money scheme is provably secure based on standard assumptions. Some constructions are relative to an oracle, others are without full security proof or are based on post-quantum indistinguishability obfuscation, which is not known to exist based on standard assumptions.
Franchised quantum money is an intermediate notion. Here, verification uses a franchised key: a unique key the bank creates for every user in the system. The main drawback is there must be a cap, decided in advance, on the number of franchised keys.
The keyless variant is the most powerful one, yet it is the weirdest: here, there is no master secret key used for minting nor a master verification key. Instead, everyone can create a quantum money state with an associated public key. The unforgeability guarantee is that a quantum polynomial-time adversary cannot create two quantum states that would pass verification with respect to the same public key (except with negligible probability). How is that possible? Here we must use the no-rewinding lemon: the minting algorithm uses a measurement for generating the public key. Running the same algorithm twice would yield two different measurement outcomes and post-measured states.
The term coined for this type of quantum money is quantum lightning, resembling the proverb "lightning never strikes the same place twice." Quantum lightning also addresses the question of verifiable randomness. Usually, we think of this public key as a form of a serial number that helps us to validate the quantum money.28 Zhandry52 suggested an alternate view: that the quantum state serves as a proof regarding some property of this serial number, and, more specifically, its randomness. Of course, the serial number itself is just a fixed string. What is argued is the process that produced that serial number must generate randomness. More precisely, consider the process that generated the quantum lightning state and the serial number, and think of the serial number as a random variable. This random variable must have a high min-entropy. Why? Suppose it had logarithmic min-entropy. Then, by running the process polynomially many times, we would end up with two states that pass verification with the same serial number, violating the security definition of quantum lightning.
Classical verifiability, proof of destruction, and uncloneable signatures. Consider private quantum money. To verify the money, the user must send the quantum money state for verification to the bank via quantum communication. In classically verifiable schemes, this can be achieved by an interactive protocol with only classical communication: usually, the bank sends some challenge message to the user (for eample, specifying in which basis every qubit should be measured),41 and the user sends an answer to the challenge (in the previous example, the measurement outcomes). The user should not be able to pass strictly more than n verifications given n quantum money states. One way of using that is the user could attach an ID of another user in response to the challenge. Upon successful verification, the bank could mint fresh quantum money and send it to the recipient.
In other schemes, there is a non-interactive Proof of Destruction (PoD): there is a way for the user to generate a proof that the money has been destroyed. Since PoD is a non-interactive process, some attention is required: the user might try to claim the money has been destroyed to several different bank branches. Therefore, this form of Proof of Destruction cannot support multiple non-communicating bank branches (which Wiesner's money definitely can).
In the most advanced form, the quantum state can be used to sign an arbitrary message. The unforgeability guarantee is that generating n + 1 different signed messages is impossible given n such states. In the keyless variant, the adversary's goal is to generate two distinct signed messages associated with the same public key.
Here is a motivating example for uncloneable signatures outside financial settings: Suppose Alice goes on vacation and wants Bob to be able to sign a message on her behalf while she is away. If she gives Bob her standard digital signature signing key, Bob would be able to sign an arbitrary number of messages on her behalf. Instead, Alice could generate an un-cloneable quantum signing key that would allow Bob to sign at most one (arbitrary) message.
Classical generation. In most of the schemes discussed, the generation of the quantum state is done by the party who holds the secret key. In schemes with classical generation (in the context of money, this is often called classical minting), the generation is an interactive protocol with classical communication between the user and the party holding the secret key. Schemes with classical verifiability and classical generation are called semi-quantum since the party holding the secret key (for example, the bank) need not have quantum resources.
Indistinguishable copies. In most cases, the quantum state has some classical information attached to it, such as the serial number in Wiesner's scheme. This serial number and distinguishing features of the quantum money state can be used to trace users and to violate their privacy. In a scheme with indistinguishable copies, all the quantum states are exact copies of each other, which assures untraceability. Quantum money with this feature is called a quantum coins scheme since coins—unlike banknotes—do not carry a serial number. The techniques for constructing quantum coins are often related to pseudorandomness.
The mini-scheme technique. In a (full) money scheme, an adversary breaks the unforgeability property by passing n + 1 verifications, given only n quantum banknotes from the bank. A quantum mini-scheme provides a weaker guarantee: the adversary breaks the unforgeability by succeeding in passing 2 verifications given a single banknote. There are techniques to lift any quantum money mini-scheme to a full scheme, with the additional assumption that post-quantum one-way functions exist. Mini-schemes were first introduced in the context of public quantum money in Aaronson and Christiano2 but can also be used in other settings.
Public quantum money resembles cash: verification can be done without the bank, using the bank's public key.
The lifting of a public quantum money mini-scheme to a full scheme is achieved as follows: The bank generates a digital signature key-pair as the public quantum money secret key and public key. To generate a banknote, the bank generates a single mini-scheme banknote and signs the mini-scheme's public key. The full scheme verification is done by running the mini-scheme's public verification, and checking the public key has a valid signature by the bank.
In the context of uncloneable signatures, there is another simplification. In a full scheme, multiple quantum signing keys can be generated, and each one can sign an arbitrarily long message. The unforgeability guarantee is that an adversary that is given n quantum signing keys cannot produce n + 1 distinct messages. In a mini-scheme, a single quantum signing key is generated and can be used to sign only one bit. In a mini-scheme, it should be intractable to sign both 0 and 1 using a single quantum signing key (except with negligible probability). To support arbitrary long messages, the lifting of a mini-scheme to a full scheme for uncloneable signatures also uses the hash-and-sign paradigm (see Ben-David and Sattah12 and Blum and Micali13 for details).
The hidden subspace technique. Aaronson and Christiano2 introduced the subspace hiding technique, which proved useful in several uncloneable primitives. Suppose S is a random 
dimensional subspace of 
. We define the subspace state, denoted |S〉 as 
. This state has a number of useful properties:
- Given a basis for S, the state |S〉 can be prepared efficiently. This allows the bank to generate a banknote.
- Given oracle access to membership in S and S⊥, the 2-outcome measurement {|S〉〈S|, I − |S〉〈S|} can be implemented efficiently, where
- This property allows public verification by the users, assuming access to these membership oracles.
- Given a single copy of |S〉, it is impossible to efficiently clone this state, even with oracle access to membership in S and S⊥, except with negligible probability. This property is sufficient to prove unforgeability.
These items were used by Aaronson and Christiano2 to construct a public quantum money mini-scheme relative to an oracle. Aaronson and Christiano also provided a construction without an oracle, but it was broken in multiple works—see Roberts and Zhandry44 and references therein. To recover from that attack, Zhandry52 showed that instead of the membership oracles, the bank could use indistinguishability obfuscation (iO) to obfuscate these subspace membership functions while preserving the security of the scheme. For more details regarding iO—a cryptographic tool so powerful that it is often referred to as crypto-complete—see Barak.9
The hidden-subspace technique can also be used to construct a public uncloneable signature mini-scheme.
- Given a single copy of |S〉, one can find a non-zero element of S by measuring it in the standard basis, or a nonzero element of S⊥ by measuring |S〉 in the Hadamard basis. Here, |S〉 serves as the quantum signing key, a non-zero element in S serves as a signature of 0, and a non-zero element of S⊥ serves as a signature of 1. The signatures could be easily verified using the subspace membership oracles.
- Given a single copy of |S〉, it is impossible to find a non-zero element of S and a non-zero element of S⊥, even with oracle access to membership in S and S⊥, except with negligible probability. This property is sufficient to prove the unforgeability of the uncloneable signature scheme.
For more details regarding these items, see Ben-David and Sattath.13 Coladangelo et al.24 also showed how the oracles could be removed by obfuscating the subspace membership functions.c The hidden-subspace technique was also used in quantum copy-protection.
Quantum Pseudorandomness
Pseudorandomness plays a crucial role in cryptography, as well as in theory of computer science. Pseudorandom states (PRS) is a family of efficiently generated quantum states {|Ψk〉}k∈{0,1}m such that it is computationally hard to distinguish between polynomially many copies of: (a) |Ψk〉 sampled uniformly from the family, and (b) a uniformly (Haar) random quantum state.35
The notion of a PRS family is a variant of quantum state t-designs:4 t-designs offer statistical rather than mere computational indistinguish-ability but have the drawback that they are only secure in the presence of t copies, where t is predetermined. Pseudorandom states remain computationally secure regardless of the number of states produced.
The simplest construction of pseudorandom states is the following. Let PRF: K × X → {0,1} be family of pseudorandom functions. Let 
. Brakerski and Shumeli15 proved the family {|Ψk〉}k∈K is a PRS family. This proved a conjecture by Ji, Liu, and Song,35 and simplified their earlier construction.
Kretschmer36 proved that, to some extent, pseudorandom states are weaker than one-way functions, arguably the minimal assumption in classical cryptography: he illustrated there is no black-box reduction from pseudorandom states to one-way functions. Note that the construction mentioned previously is a black-box reduction in the opposite direction. Kretschmer's result raises the possibility of basing quantum cryptography on pseudorandom states—an assumption that may be weaker than the existence of one-way functions. Indeed, several recent results show how to construct basic cryptographic tasks based on PRS (or its variants). Notable examples are: a computationally hiding and statistically binding quantum commitment scheme,8,38 private quantum coins,35 almost public quantum coins11 and Lamport (that is, one-time secure) signatures with quantum public keys,38 symmetric encryption with quantum ciphers,8 quantum multi-party computation for classical circuits8,38 and asymmetric encryption with quantum public keys.10,23 The last two applications are especially unexpected because, classically, they cannot be constructed via black-box from oneway functions. A comprehensive graph presenting the various notions of quantum pseudorandomness and their applications is available at https://sattath.github.io/qcrypto-graph/. A remaining open question is whether digital signatures are implied by pseudo-random states.
We mention briefly that a similar approach can be used to define pseudorandom unitaries and unitary t-designs. Pseudorandom unitaries and unitary t-designs can be used to generate a state t-design, but not conversely. There are still no constructions for pseudorandom unitaries, though Ji, Liu and Song35 suggest two constructions that they conjecture to be secure. Their first construction is based on pseudorandom functions, and another is based on pseudorandom permutations.
Table 2 presents the classical analogs of the quantum pseudorandom objects.
Table 2. Classical and quantum forms of pseudorandomness.
Quantum Copy-Protection
Software companies want to sell programs that can be used offline by the customers (even if the installation requires online communication). On the other hand, they want to restrict users from sharing the programs with others. Classically, this restriction cannot be enforced: a pirate could always create a perfect copy of the computer with the installed program, including all its component (the hard disk drive, CPU, memory, etc.), and at this point, both computers would have a working copy of the program.
Quantum copy protection is a compiler that receives a classical program (for example, the source code, or a Boolean circuit) as the input, and returns a copy-protected program in the form of a quantum state. This copyprotected program can be used to run the program on any input, as many times as the user wishes.
The security guarantee is the following. A challenger samples a program P from a distribution over programs P. The pirate is given the copy-protected state of the program P. The pirate uses this state and sends two states to two freeloaders. Then, a random challenge x is sampled and handed to both freeloaders, and each freeloader sends back yi, which is their attempt to compute P(x). Note that the freeloaders cannot communicate at this point. They win if y0 = y1 = P(x). Note that one freeloader could easily compute P (x) correctly: the pirate could send the copy-protected program to the first freeloader, which the freeloader could use to evaluate P(x). The seconder freeloader would have to guess P(x); therefore, the chances could be slim for certain distributions P.
A distribution over programs p is quantum learnable if the program can be learned efficiently from its input-output behavior with a quantum computer. It is impossible to copy-protect a learnable distribution: the pirate could learn the program using one copy of the copy-protected program and send the insights from the learning phase to the freeloaders.
This security definition can be easily strengthened so there are n copy-protected programs and n + 1 freeloaders, and cases where the challenge input x is not necessarily uniformly random.
There are constructions for quantum copy-protection for any unlearnable family relative to quantum1 and classical3 oracles, and no construction is known in the plain model for any class. Ananth and La Placa7 introduced a weaker form called secure software leasing (SSL), which allows for copy-detection, and showed a construction for some unlearnable family. Their construction completely reveals the software, but a pirated copy can be detected by honest users. On the negative side, they constructed a quantum un-learnable family that cannot be SSLed (and hence, cannot be copy-protected as well).
To this day, copy protection of quantum circuits has not been studied.
One-time programs. One may consider a variant of quantum copy-protection in which the user can evaluate the program only once.17 One could hope that measuring the output would collapse the quantum state, causing it to self-destruct, similarly to uncloneable signatures. Unfortunately, one-time programs are impossible to construct, even with computational assumptions.1 Why is that? Suppose the evaluation gives the correct answer without any errors (that is, with probability 1). In this case, the post-measured state remains exactly the same prior to the measurement and therefore does not self-destruct. It can be shown based on the "Almost good as new lemma" that if the correct outcome occurs with probability 1 − ε, the trace distance between the pre-measured state and the post-measured state is 
, see [Lemma 4],1 and therefore can be ignored as long as ε is negligible. Suppose errors occur with constant error, say, 
. In that case, the adversary could use k copies of the program to create an enhanced program, in which the error happens with probability 2-ω(k) by standard error-reduction techniques. This technique allows a user with k copies to evaluate the function on a number of points that is exponential in k.
Broadbent, Gutoski, and Stebila17 showed how to construct quantum one-time programs in a (non-standard) model in which one-time classical memory exists. A one-time memory is a box that can store two bits. The user can ask the box for one of the bits and receive the answer, but at this point, the box self-destructs, and the user has no way of retrieving the other bit. One-time memory is an idealized, non-interactive version of 1-of-2 oblivious transfer. A construction of one-time classical programs was already known based on the same assumption.32 Broadbent et al.16 and Coladangelo22 show how to construct one-time programs in other non-standard models.
Uncloneable Forms of Encryption
Uncloneable encryption. In classical encryption schemes, an eavesdropper can always copy the ciphertext. In uncloneable quantum encryption, a classical plaintext is encrypted to a quantum ciphertext. The security guarantee is there is no way for an eavesdropper to manipulate the ciphertext and send it to two isolated parties so that both parties could correctly decrypt it, even after they are provided with the secret key.
Here is a motivating example for uncloneable encryption. Consider an adversary who can somehow break the encryption scheme and learn the secret key for the ciphertext, but this process is slow. One such instance is an adversary who expects to have a quantum computer (which we know can break most contemporary public-key encryption schemes) in the coming years. With an uncloneable encryption scheme, this approach becomes moot since the adversary cannot copy the ciphertext without being detected: if the eavesdropper tries to keep a state which would be enough to recover the plaintext at a later time, this necessarily means that the intended recipient, which has the secret key, would not be able to decrypt the original message that was sent.
Tamper-evident quantum encryption is a weaker variant first introduced by Gottesman:33 tamper-evident encryption is to uncloneable encryption what SSL is to copy-protection. Several definitions and constructions in the spirit of the informal one given here were first shown by Broadbent and Lord19 for symmetric uncloneable encryption. Ananth and Kaleoglu6 have extended this notion to the asymmetric setting. Furthermore, they showed that a strong uncloneable encryption variant implies a weak copyprotection form for a family of point functions.
Quantum encryption with certified deletion. Alice has a terminal illness and wants Bob to have all her passwords once she passes away. She encrypts her message and sends the ciphertext to Bob, and the decryption key to her lawyer, who is ordered to send the secret key to Bob upon her death.
Suddenly, a cure for Alice's illness is found, and she wants to ensure her passwords will not leak. Even if Bob complies, there is no way to certify that he had not saved a copy unbeknownst to Alice. Quantum encryption with certified deletion is an encryption scheme of classical messages with quantum ciphertexts that, in addition to a standard privacy guarantee, allows Bob to prove that he deleted the ciphertext and would not be able to decrypt the passwords even should he learn the decryption key.18,34 More precisely, an interactive protocol with classical communication can be used to revoke Bob's ciphertext. A successful revocation guarantees that even if Bob gets the decryption key after the revocation, he would not be able to decrypt the passwords.
Revocable quantum timed-release encryption. Suppose Alice wants to send Bob a message that he could read only one year ahead. In a (classical) timed-release encryption, the encryption is efficient, but decrypting the ciphertext requires a number of computational steps that Alice can choose upon encryption. Assuming Alice can estimate Bob's computer clock rate, she could set the encryption parameters so that Bob could recover her message from the ciphertext a year ahead.
However, suppose, as in the example with Alice's terminal illness, a cure is found after only one month. As was already discussed in the context of quantum encryption with certified deletion, revoking a classical encryption in this setting is impossible. In a revocable quantum timed-release en-cryption,48 the ciphertext is quantum, and there is a protocol that allows Bob to prove that he deleted the quantum ciphertext before the time-release deadline arrives—that is, the one year mentioned in the example. The main advantage of using quantum timed-release encryption (over quantum encryption with certified deletion) is that there is no need to use a trusted party—the lawyer in the earlier example.
Uncloneable decryptors. Subscription-based satellite television works roughly as follows: the TV shows are encrypted, and the satellite broadcasts the shows in encrypted form, which can be received by anyone with a satellite dish. Paying customers receive a smart-card containing a decryption key that allows them to view the television shows. The problem? A sophisticated pirate can create many copies of the smart-card. This attack is not merely a theoretical risk: see https://en.wikipedia.org/wiki/Conditional_access for a list containing systems known to be compromised.
Uncloneable cryptography makes little sense without long-term quantum memory.
A (symmetric or asymmetric) encryption scheme with uncloneable decryptors is a scheme that can be used to produce uncloneable quantum decryption keys.30,45 The decryptor can be used to decrypt the (classical) cipher-texts: The decryptor allows the subscribers to watch the TV shows in the example. The uncloneability feature guarantees that an adversary that receives a decryptor state should not be able to produce two states given to two distinguishers, that could use it to win the standard semantic security indistinguishability game. This notion can be generalized to support k decryptors and ℓ > k distinguishers.
Discussion
Quantum key distribution (QKD) has been commercially available for two decades; quantum computers are being developed by several industry giants hoping to demonstrate quantum advantage with real impact soon.
Uncloneable cryptography, for the most part, makes little sense without long-term quantum memory. For example, one of the functions of money is as a store of value. Quantum money, which could not be stored even for a second—more than the lifetime of the qubits in all the major quantum computing platforms being developed—would not be particularly useful. It remains to be seen whether unclone-able cryptography would have applications in the coming, noisy intermediate-scale quantum (NISQ) era.
Acknowledgments
This work was supported by the Israel Science Foundation (ISF) grants No. 682/18 and 2137/19 and by the Cyber Security Research Center at Ben-Gurion University. We thank Dean Doron for valuable discussions regarding various notions of pseudorandomness, Shai Wyborski for his comments, and Vince Serrano for his illustration in Figure 1.
This work has received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (grant agreement No 756482).
References
1. Aaronson, S. Quantum copy-protection and quantummoney. In Proceedings of the 24th Annual IEEE Conf. on Computational Complexity, (Paris, France, July 15–18, 2009). IEEE Computer Society, 229–242; https://doi.org/10.1109/CCC.2009.42, arXiv:1110.5353.
2. Aaronson, S., and Christiano, P. Quantum money from hidden subspaces. Theory of Computing 9, (2013), 349–401; https://doi.org/10.4086/toc.2013.v009a009, arXiv:1203.4740.
3. Aaronson, S. et al. New Approaches for Quantum Copy-Protection. In Proceedings of CRYPTO 2021 LNCS 12825, 1. Springer, 526–555; https://doi.org/10.1007/978-3-030-84242-0_19, arXiv:2004.09674.
4. Ambainis, A., and Emerson, J. Quantum t-designs:t-wise independence in the quantum world. In Proceedings of the 22nd Annual IEEE Conf. on Computational Complexity, (San Diego, CA, USA, June 13–16, 2007). IEEE Computer Society, (2007), 129–140; https://doi.org/10.1109/CCC.2007.26, arXiv:quantph/0701126.
5. Amos, R. et al. One-shot signatures and applications to hybrid quantum/classical authentication. In Proceedings of the 52nd Annual ACM SIGACT Symp. on Theory of Computing, (Chicago, IL, USA, June 22–26, 2020). K. Makarychev et al. (eds), ACM, 255–268; https://doi.org/10.1145/3357713.3384304, Cryptology ePrint Archive:Report 2020/107.
6. Ananth, P., and Kaleoglu, F. Unclonable encryption, revisited. In Proceedings of TCC 2021, LNCS 13042, 1. Springer, (2021), 299–329; https://doi.org/10.1007/978-3-030-90459-3_11, arXiv:2103.15009.
7. Ananth, P., and La Placa, R.L. Secure software leasing. In Proceedings of Advances in Cryptology (Zagreb, Croatia, Oct. 17–21, 2021). LNCS 12697. A. Canteaut, and F. Standaert, (eds), Springer, 501–530; https://doi.org/10.1007/978-3-030-77886-6_17, arXiv:2005.05289.
8. Ananth, P. et al. Cryptography from pseudorandom quantum states. In Proceedings of Advances in Cryptology (Santa Barbara, CA, USA, Aug. 15–18, 2022), LNCS 13507. Y. Dodis, and T. Shrimpton, (eds), Springer, 208–236; arXiv:2112.10020.
9. Barak, B. Hopes, fears, and software obfuscation. Commun. ACM. 59, 3 (Mar. 2016), 88–96; https://doi.org/10.1145/2757276, Cryptology ePrint Archive:Report 2016/210.
10. Barooti, K. et al. Public-key encryption with quantum keys. Cryptology ePrint Archive, Paper 2023/877, (2023); https://eprint.iacr.org/2023/877.
11. Behera, A., and Sattath, O. Almost public coins. (2020); arXiv:2002.12438.
12. Behera, A. et al. Noise-tolerant quantum tokens for MAC. (2021); arXiv:2105.05016.
13. Ben-David, S., and Sattath, O. Quantum tokens for digital signatures. Quantum 7, (2023), 901;. https://doi.org/10.48550/ARXIV.1609.09047.
14. Blum, M., and Micali, S. How to generate cryptographically strong sequences of pseudorandom bits. SIAM J. Comput. 13, 4 (1984), 850–864; https://doi.org/10.1137/0213053.
15. Brakerski, Z., and Shmueli, O. (Pseudo) random quantum states with binary phase. In Proceedings of the 17th Intern. Conf on Theory of Cryptography LNCS. Springer, 2019, 229–250; https://doi.org/10.1007/978-3-030-36030-6_10, arXiv:1906.10611.
16. Broadbent, A. et al. Towards quantum one-time memories from stateless hardware. Quantum 5, (2021), 429; https://doi.org/10.22331/q-2021-04-08-429, arXiv:1810.05226.
17. Broadbent, A. et al. Quantum one-time programs (extended abstract). In Proceedings of the 17th Annual Intern. Conf. on Cryptology (Santa Barbara, CA, USA, Aug. 18–22, 2013), LNCS, 8043. R. Canetti, and Garay, J.A. (eds). Springer, 344–360; http://eprint.iacr.org/2013/343, arXiv:1211.1080.
18. Broadbent, A., and Islam, R. Quantum encryption with certified deletion. In Proceedings of the 18th Intern. Conf. on Theory of Cryptography (Durham, NC, USA, Nov. 16–19, 2020), LNCS Part III, 12552. R. Pass, and K. Pietrzak, (eds), Springer, 92–122; https://doi.org/10.1007/978-3-030-64381-2_4, arXiv:1910.03551.
19. Broadbent, A., and Lord, S. Uncloneable quantum encryption via oracles. In TQC 2020, LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 4: 1–4: 22; https://doi.org/10.4230/LIPIcs.TQC.2020.4, arXiv:1903.00130.
20. Bruß, D. et al. Optimal universal and state-dependent quantum cloning. Phys. Rev. A. 57, 4 (1998), 2368–2378; https://doi.org/10.1103/PhysRevA.57.2368, arXiv:quant-ph/9705038.
21. Carter, L., and Wegman, M.N. Universal classes of hash functions. J. Comput. Syst. Sci. 18, 2 (1979), 143–154; https://doi.org/10.1016/0022-0000(79)90044-8.
22. Chung, K. et al. Cryptography with disposable backdoors. Cryptogr. 3, 3 (2019), 22; https://doi.org/10.3390/cryptography3030022, Cryptology ePrint Archive: Report 2018/352.
23. Coladangelo, A. Quantum trapdoor functions from classical one-way functions. Cryptology ePrint Archive, Paper 2023/282, (2023); https://eprint.iacr.org/2023/282.
24. Coladangelo, A. et al. Hidden costs and applications to unclonable cryptography. In Proceedings of the 41st Annual Intern. Conf. Advances in Cryptology (Virtual Event, Aug. 16–20, 2021), LNCS 12825. T. Malkin, and C. Peikert, (eds). Springer, 556–584; https://doi.org/10.1007/978-3-030-84242-0_20, Cryptology ePrint Archive:Report 2021/946.
25. Coladangelo, A., and Sattath, O. A quantum money solution to the blockchain scalability problem. Quantum 4, (July 2020), 297; https://doi.org/10.22331/q-2020-07-16-297, arXiv:2002.11998.
26. Dankert, C. et al. Exact and approximate unitary 2-designs and their application to fidelity estimation. Phys. Rev. A 80, 7 (2009); https://doi.org/10.1103/PhysRevA.80.012304, arXiv:quant-ph/0606161v2.
27. Dieks, D. Communication by EPR devices. Physics Letters A 92, 6 (1982), 271–272; https://doi.org/10.1016/0375-9601(82)90084-6.
28. Farhi, E. et al. Quantum money from knots. In Proceedings of Innovations in Theoretical CS 2012, (Cambridge, MA, USA, January 8–10, 2012). S. Goldwasser, (ed), ACM, 276–289; https://doi.org/10.1145/2090236.2090260, arXiv:1004.5127.
29. Gavinsky, D. Quantum money with classical verification. In Proceedings of the 27th Conf. on Computational Complexity, (Porto, Portugal, June 26–29, 2012.) IEEE Computer Society, 42–52; https://doi.org/10.1109/CCC.2012.10, arXiv:1109.0372.
30. Georgiou, M., and Zhandry, M. Unclonable decryption keys. Cryptology ePrint Archive, Paper 2020/877 (2020); https://eprint.iacr.org/2020/877.
31. Goldreich, O. et al. How to construct random functions. J. ACM 33, 4 (1986), 792–807; https://doi.org/10.1145/6490.6503.
32. Goldwasser, S. et al. One-time programs. In Proceedings of the Advances in Cryptology 2008. LNCS, 5157. D.A. Wagner, (ed), Springer, 39–56; https://doi.org/10.1007/978-3-540-85174-5_3.
33. Gottesman, D. Uncloneable encryption. Quantum Inf. Comput. 3, 6 (2003), 581–602; https://doi.org/10.26421/QIC3.6-2, arXiv:0210062.
34. Hiroka, T. et al. Quantum encryption with certified deletion, revisited: Public key, attribute-based and classical communication. ASIACRYPT 13090, LNCS. Springer, 2021, 606–636; https://doi.org/10.1007/978-3-030-92062-3_21, arXiv:2105.05393.
35. Ji, Z. et al. Pseudorandom quantum states. In Proceedings of the 2018 Conf. on Advances in Cryptology, (Santa Barbara, CA, USA, Aug. 19–23, 2018). LNCS. H. Shacham, and A. Boldyreva, (eds), Springer, 126–152; https://doi.org/10.1007/978-3-319-96878-0_5, arXiv:1711.00385.
36. Kretschmer, W. Quantum pseudorandomness and classical complexity. In Proceedings of the 16th Conf. on the Theory of Quantum Computation, Communication and Cryptography, (Virtual Conf. July 5–8, 2021), 2: 1–2:20. M. Hsieh, (ed). Schloss Dagstuhl - Leibniz-Zentrum für Informatik; https://doi.org/10.4230/LIPIcs.TQC.2021.2, arXiv:2103.09320.
37. Molina, A. et al. Optimal counterfeiting attacks and generalizations for wiesner's quantum money. In TQC 2012, LNCS 7582. Springer, 45–64; https://doi.org/10.1007/978-3-642-35656-8_4, arXiv:1202.4010.
38. Morimae, T., and Yamakawa, T. Quantum commitments and signatures without one-way functions. In Proceedings of the 42nd Annual Intern. Cryptology Conf. on Advances in Cryptology (Santa Barbara, CA, USA, Aug. 15–18, 2022). Y. Dodis, and T. Shrimpton, (eds), Springer, 269–295; arXiv:2112.06369.
39. Mosca, M., and Stebila, D. Quantum coins. Contemp. Math 523, (2010), 35–47. Amer. Math. Soc.; https://doi.org/10.1090/conm/523/10311, arXiv:0911.1295.
40. Park, J.L. The concept of transition in quantum mechanics. Foundations of Physics 1, 1 (1970, 03), 23–33; https://doi.org/10.1007/BF00708652.
41. Pastawski, F. et al. Unforgeable noise-tolerant quantum tokens. Proceedings of the National Academy of Sciences 109, 40 (2012), 16079–16082; https://doi.org/10.1073/pnas.1203552109, arXiv:1112.5456.
42. Pena, M.C. et al. Non-quantum cryptanalysis of the noisy version of Aaronson-Christiano's quantum money scheme. IET Information Security 13, 4 (2019), 362–366; https://doi.org/10.1049/iet-ifs.2018.5307.
43. Radian, R., and Sattath, O. Semi-quantum money. J. Cryptol. 35, 2, (2022), 8; https://doi.org/10.1007/s00145-021-09418-8, arXiv:1908.08889.
44. Roberts, B., and Zhandry, M. Franchised quantum money. In Proceedings of ASIACRYPT 2021 LNCS 13090, 1, 549–574; https://doi.org/10.1007/978-3-030-92062-3_19, arXiv:2110.09733.
45. Sattath, O., and Wyborski, S. Uncloneable decryptors from quantum copy-protection. (2022); arXiv:2203.05866.
46. Shmueli, O. Public-Key Quantum money with a classical bank. In Proceedings of 2022 STOC. ACM, 790–803; https://doi.org/10.1145/3519935.3519952. Cryptology ePrint Archive: Report 2021/1427.
47. Shmueli, O. Semi-quantum tokenized signatures. In Proceedings of the 42nd Annual Intern. Conf. on Advances in Cryptology (Santa Barbara, CA, USA, Aug. 15–18, 2022), LNCS 13507. Y. Dodis, and T. Shrimpton, (eds), Springer, 296–319. Cryptology ePrint Archive:Report 2022/228.
48. Unruh, D. Revocable quantum timed-release encryption. J. ACM 62, 6 (2015), 49:1–49:76; https://doi.org/10.1145/2817206, Cryptology ePrint Archive:Report 2013/606.
49. Werner, R.F. Optimal cloning of pure states. Phys. Rev. A. 58, 9 (1998), 1827–1832; https://doi.org/10.1103/PhysRevA.58.1827, arXiv:quant-ph/9804001.
50. Wiesner, S. Conjugate coding. SIGACT News 15, 1 (1983, 01), 78–88; https://doi.org/10.1145/1008908.1008920.
51. Wootters, W., and Zurek, W. A single quantum cannot be cloned. Nature 299, 5886 (1982), 802–803; https://doi.org/10.1038/299802a0.
52. Zhandry, M. Quantum lightning never strikes the same state twice. Or: Quantum money from cryptographic assumptions. J. Cryptol. 34, 1, (2021), 6. Cryptology ePrint Archive:Report 2017/1080.
Footnotes
a. The first version of this manuscript was submitted circa 1969.
b. Stronger in the sense that every public quantum money scheme is also a private quantum money scheme, but the converse does not hold.
c. They also change the scheme slightly: for technical reasons which are outside the scope of this work, they use a novel related notion called coset states instead of the subspace states that were introduced earlier.
The Digital Library is published by the Association for Computing Machinery. Copyright © 2023 ACM, Inc.
No entries found