Contributed Talk 2c

Abstract: Quantum information allows us to build quantum money schemes, where a bank can issue banknotes in the form of authenticatable quantum states that cannot be cloned or counterfeited: a user in possession of k banknotes cannot produce k + 1 banknotes. Similar to paper banknotes, in existing quantum money schemes, a banknote consists of an unclonable quantum state and a classical serial number, signed by the bank. Thus, they lack one of the most fundamental properties cryptographers look for in a currency scheme: privacy/anonymity. In this work, we construct the first public-key quantum coin scheme, that is, a money scheme where all banknotes are identical. Assuming existence of subspace-hiding obfuscation, we construct a public-key quantum coin scheme. Further, we show that quantum coins do not necessarily provide privacy against all adversaries. Therefore, we develop formal definitions of privacy for quantum money schemes. Then, we construct the first public-key quantum money schemes that satisfy these security notions. Namely, assuming existence of indistinguishability obfuscation (iO) and hardness of Learning with Errors (LWE), we construct a public-key quantum money scheme with anonymity against users and traceability by authorities. a public-key quantum money scheme with untraceability (i.e. not even the bank/authorities can track banknotes). As another application, we show that the no-cloning principle allows us to construct schemes, with advanced security guarantees that are classically impossible, for a seemingly unrelated application: voting! Assuming existence of iO and hardness of LWE, we construct a universally verifiable quantum voting scheme with classical votes. Finally, to achieve our results, we develop a variety of technical tools, which we believe might be of independent interest. We show a new result called quantum-state read-once small-range distributions, which shows how to simulate superposition query access to an exponential size oracle with quantum-state outputs using single copy each of polynomially many state samples. We construct a deterministic classical signature scheme secure against quantum-query access to the signing oracle. We construct publicly rerandomizable encryption with strong correctness from LWE, where no adversary is able to produce a malicious ciphertext and a malicious random tape such that the ciphertext before and after rerandomization (with the malicious tape) decrypts to different values.

Abstract: Recent work of Bostanci, Nehoran, Zhandry (STOC'25, QIP'25) formalized the notion of quantum fire: A quantum state that can be cloned efficiently but cannot be converted to a classical string. Nehoran and Zhandry (QIP'23) gave a construction of quantum fire relative to an (inefficient) unitary quantum oracle, and proved its correctness and security. Bostanci et al (STOC'25, QIP'25) gave a candidate construction of quantum fire based on cryptographic group action assumptions, and proved its correctness. However, they do not have a proof of security, and the security is only conjectured without any justification at all. In this work, we give the first construction of (public-key) quantum fire relative to a classical oracle, and prove its correctness and security. This resolves the open question posed by Bostanci et al (STOC'25, QIP'25) and Nehoran and Zhandry (QIP'23). Further, assuming existence of one-way functions, our scheme can also be made efficient. We note that, even in the unitary quantum oracle setting, no efficient quantum fire scheme existed: Nehoran-Zhandry show that their unitary oracle cannot be made efficient. Implications to Physics: In quantum mechanics, various fundamental principles called no-go properties exist, such as no-cloning theorem, no-hiding theorem, no-deleting theorem, no-telegraphing theorem and so on. Most of these no-go properties have been shown to be equivalent to each other. However, our result gives the first (classical oracle) separation between no-go properties of quantum mechanics! Our result means that, relative to a classical oracle, no-telegraphing does not imply no-cloning. Note that, in the information-theoretic setting, no-cloning and no-telegraphing are equivalent. Our result means that the equivalency of the fundamental no-go principles of quantum mechanics that we take for granted might not hold in a computational world!

Abstract: The no-cloning theorem leads to information-theoretic security in various quantum cryptographic protocols. However, this security typically derives from a possibly weaker property that classical information encoded in certain quantum states cannot be broadcast. To formally capture this property, we introduce the study of ``orthogonality broadcasting." When attempting to broadcast the orthogonality of two different qubit bases, we establish that the power of classical and quantum communication is equivalent. However, quantum communication is shown to be strictly more powerful for broadcasting orthogonality in higher dimensions. We then relate orthogonality broadcasting to quantum position verification and provide a new method for establishing error bounds in the no pre-shared entanglement model that can address protocols previous methods could not. Our key technical contribution is an uncertainty relation that uses the geometric relation of the states that undergo broadcasting rather than the non-commutative aspect of the final measurements.

Abstract: Quantum no-cloning theorem gives rise to the intriguing possibility of quantum copy protection where we encode a program or functionality in a quantum state such that a user in possession of k copies cannot create k + 1 copies, for any k. Introduced by Aaronson (CCC’09) over a decade ago, copy protection has proven to be notoriously hard to achieve. Previous work has been able to achieve copy-protection for various functionalities only in restricted models: (i) in the bounded collusion setting where k → k + 1 security is achieved for a-priori fixed collusion bound k (in the plain model with the same computational assumptions as ours, by Liu, Liu, Qian, Zhandry [TCC’22]), or, (ii) only k → 2k security is achieved (relative to a structured quantum oracle, by Aaronson [CCC’09]). In this work, we give the first unbounded collusion-resistant (i.e. multiple-copy secure) copy protection schemes, answering the long-standing open question of constructing such schemes, raised by multiple previous works starting with Aaronson (CCC’09). More specifically, we obtain the following results. We construct (i) public-key encryption, (ii) public-key functional encryption, (iii) signature and (iv) pseudorandom function schemes whose keys are copy-protected against unbounded collusions in the plain model (i.e. without any idealized oracles), assuming (post-quantum) subexponentially secure iO and LWE. We show that any unlearnable functionality can be copy-protected against unbounded collusions, relative to a classical oracle. As a corollary of our results, we rule out the existence of hyperefficient quantum shadow tomography, – even given non-black-box access to the measurements, assuming subexponentially secure iO and LWE, or, – unconditionally relative to a quantumly accessible classical oracle, and hence answer an open question by Aaronson (STOC’18). We obtain our results through a novel technique which uses identity-based encryption to construct multiple copy secure copy-protection schemes from 1-copy → 2-copy secure schemes. We believe our technique is of independent interest. Along the way, we also obtain the following results. We define and prove the security of new collusion-resistant monogamy-of-entanglement games for coset states. We construct a classical puncturable functional encryption scheme whose master secret key can be punctured at all functions f such that f(m0) ̸= f(m1).