Quantum Fire with Delegated Cloning

Quantum Fire with Delegated Cloning

arXiv:2610.03593v1 [quant-ph] 2 Oct 2026

Rohit Chatterjee *

Ananta Mukherjee†

Vir Pathak‡

Supartha Podder§

Abstract Quantum fire is a recently introduced cryptographic primitive consisting of efficiently preparable quantum states, called flames, that admit efficient cloning but resist efficient telegraphing, namely reconstruction via classical communication without preshared entanglement. In all prior constructions of quantum fire, cloning is a public operation that requires no separate key and every holder of a flame state can clone it. For applications to access control, however, an issuer may wish to delegate cloning to designated quantum servers while withholding this capability from other flame holders. To address this, we introduce delegatable quantum fire, in which cloning requires a separate key. We give two constructions in the classical-oracle model. Our first construction uses a classical secret key which enables cloning, and any user with the entire key may clone successfully. Our second construction, which we call torch-fire, uses quantum cloning keys, called torches, which enable cloning while remaining unaffected in the process but cannot otherwise be split or delegated to enable additional cloning. An efficient adversary given m torches cannot, except with negligible probability, enable more than m noncommunicating parties to each clone a fresh, independently issued challenge flame. The adversary may jointly process its resources before separating the parties and distribute arbitrarily entangled registers among them. Both constructions are in the oracle model, relying on public classical oracles that allow queries in quantum superposition.

* National University of Singapore. Email: rochat@nus.edu.sg. † Centre for Quantum Technologies, National University of Singapore. Email: a.mukherjee@u.nus.edu. ‡ Stony Brook University. Email: vpathak@cs.stonybrook.edu. § Stony Brook University. Email: supartha@cs.stonybrook.edu.

1

Contents 1

Introduction 1.1 Our Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.1.1 Delegation via a Classical Secret Key . . . . . . . . . . . . . . . . . . . . . . . . 1.1.2 Delegation via an Uncloneable Quantum Key: Torch-Fire . . . . . . . . . . . . 1.2 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3 4 4 5 6

2

Technical Overview 8 2.1 One-Shot Signatures in the Classical Oracle Model . . . . . . . . . . . . . . . . . . . . 8 2.2 Delegation via a Classical Secret Key . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.3 Torch-Fire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.4 Global Non-Proliferation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

3

Preliminaries

4

Cryptographic Building Blocks 19 4.1 One-shot signatures (OSS) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 4.2 Quantum fire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

5

Quantum Fire with Classical Cloning Key

29

6

Definition: Torch-Fire

34

7

Construction of Torch-fire 7.1 Construction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.2 Correctness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.3 Untelegraphability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

37 37 44 46

8

Extraction and Global Non-proliferation 8.1 Extraction from separated computations . . . . . . . . . . . . . . . . . . . . . . . . . . 8.2 From cloning to torch signatures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.3 Global non-proliferation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

48 49 59 65

16

A Deferred details from con:cgs-algorithms 70 A.1 Coherent Tag Generation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70 A.2 Implementation Details of Cloning a flame . . . . . . . . . . . . . . . . . . . . . . . . 71 B Deferred details from con:torch-fire 71 B.1 Coherent execution of an affine query . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 B.2 Proof of Lemma 7.6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72

2

1

Introduction

The no-cloning principle [WZ82; Die82] asserts that an unknown quantum state cannot be copied in general. Since the early proposal of quantum money by Wiesner [Wie83], this principle has been the basis for a large body of work on uncloneable cryptography, which uses the impossibility of copying to obtain guarantees that have no classical analogue. Examples include quantum money and quantum lightning [AC12; Zha19], copy-protection of programs [Aar09; CLLZ21; ALLZZ21], secure software leasing [AL21; BJLPS21], uncloneable encryption [BL20; AK21], quantum witnesses and advice [BKL23; CKP25; BGPS25] and one-shot signatures [AGKZ20; SZ25] (see also [AC23] for a discussion of the different no-cloning paradigms used in such constructions). A closely related principle is that of no-telegraphing [Wer01]: an unknown quantum state cannot be converted into classical information from which it can later be reconstructed. Informationtheoretically, the two principles are equivalent. A classical description of a state can be copied freely, and so the ability to telegraph a state implies the ability to clone it. Conversely, given an unbounded number of copies of a state, one can learn a classical description of it via tomography. This second direction, however, is inherently inefficient, and it is natural to ask whether the two principles separate once we restrict ourselves to efficient computation. Quantum fire. Nehoran and Zhandry [NZ24] showed that this is indeed the case, relative to a quantum oracle. They introduced the notion of quantum fire: a family of efficiently preparable states that can be efficiently cloned by anyone, but which cannot be efficiently telegraphed, namely transmitted using only classical communication (and no pre-shared entanglement). Bostanci, Nehoran, and Zhandry [BNZ25] subsequently gave a candidate construction based on group actions, and Çakan, Goyal, and Shmueli [ÇGS26] gave the first construction of public-key quantum fire relative to classical oracles, with unconditional security in that model. In the same work, they also introduced quantum key-fire, where the flame state additionally serves as a functional key (such as a signing or decryption key) that can be cloned freely but cannot be exfiltrated into a classical string. Very recently, Casper, Nehoran, and Sattath [CNS26] gave the first construction of quantum fire in the standard model, from one-shot signatures together with indistinguishability obfuscation and LWE, and used it to obtain publicly certifiable min-entropy. Suggested applications for quantum fire have included forms of access control that are enabled by quantum computers. Roughly speaking, a flame can be replicated freely across quantum devices, but cannot be leaked or transmitted over classical channels. This, however, provides an extremely total model of control. Every entity that holds a flame is also able to clone it, and the only line being drawn is between quantum and classical communication. In many settings one could reasonably desire a more nuanced form of control, where some designated parties are allowed to replicate flames, while others, even those with quantum computers and with flames in hand, are not. As an informal example, an issuing authority may want a few trusted servers to be able to replicate credentials as demand requires, without every holder of a credential gaining the same ability. This leads to the following question. Question 1: Can quantum fire be augmented so that only parties holding an appropriate key can clone flames, while flames remain untelegraphable? We emphasize that for such a guarantee to be meaningful, uncloneability for parties without the key must be functional: such a party should not be able to produce two states that each pass verification, irrespective of whether these states are copies of the original flame. In this sense, flames should behave like uncloneable states to those without the key, and like quantum fire to those with it. 3

The nature of the key. The answer to Question 1 depends quite crucially on what kind of key is used to delegate cloning. The simplest choice is a classical secret key. However, a classical key can itself be copied and handed out arbitrarily, and so any party that is ever given cloning power can grant it to as many others as it likes. The issuing authority therefore has no control over the number of parties that are eventually able to clone. To retain such control, the key must itself be quantum, and must resist duplication. At the same time, a quantum key that is consumed upon use, as is the case with signing tokens [BS23] or the signing state of a one-shot signature [AGKZ20], would only permit a bounded number of cloning operations. Ideally, we would like a key that can be used to clone repeatedly while remaining intact, but which still cannot be used to grant cloning power at more locations than there are keys. This raises a second question. Question 2: Is there a reusable quantum cloning key, such that m such keys cannot be used to enable cloning at more than m separate locations? We note that formalizing Question 2 already requires some care. An adversary holding m keys need not split them up in the obvious way. It may instead jointly process its keys and flames, and distribute arbitrarily entangled registers among a larger number of parties, in the hope that more than m of them are subsequently able to clone. A meaningful definition must account for such strategies.

1.1

Our Results

In this work, we study the notion of quantum fire with delegatable cloning, which augments quantum fire so that only authorized users holding the right kind of key are able to clone flames, while users without a key remain unable to clone even in the functional sense above. We give two constructions, both in the classical oracle model (i.e., relative to classical oracles that may be queried in superposition), achieving different flavors of this guarantee. Our first construction gives a positive answer to Question 1 using a classical secret key, and our second construction gives a positive answer to Question 2 using reusable quantum keys, which we call torches. 1.1.1

Delegation via a Classical Secret Key

Our first construction considers the setting where a classical secret key is required to clone, and any user with the entire key may clone successfully. In this construction, flames are privately verifiable, and the same secret key is used both to verify and to clone flames. Flames can be cloned for a bounded number of generations, and each flame keeps track of how many further clones are possible. Theorem 1.1 (Informal). Relative to classical oracles, there exists a privately verifiable quantum fire scheme with a classical secret cloning key, in which flames can be cloned up to O(log λ) generations by any user holding the key, are uncloneable for any efficient (quantum) adversary that does not hold the key, and are untelegraphable. At a high level, our construction builds on one-shot signatures in the classical oracle model of Shmueli and Zhandry [SZ25], and on the quantum fire construction of Casper, Nehoran, and Sattath [CNS26], where a flame is a one-shot signing state accompanied by a chain of signatures certifying its provenance. Signing in the scheme of [SZ25] requires access to a classical dual oracle, which is not needed for key generation or verification, and we use this oracle as the secret cloning key. Our analysis relies on the delayed collapsing property of this scheme, recently established by Bartusek et al. [BGMS25a]. We give an overview of the construction and its analysis in Section 2.2. 4

1.1.2

Delegation via an Uncloneable Quantum Key: Torch-Fire

As discussed above, a classical cloning key offers no control over how many parties can eventually clone. Our second construction, which we call Torch-Fire, addresses this with quantum keys. A torch-fire scheme separates the publicly verifiable quantum states, which we call flames, from reusable quantum cloning authorities, which we call torches. The issuing authority prepares some number R of torches during setup, each associated with a public identifier, and is the only party that can create fresh flames. Anyone can verify a flame using only public information. A party holding a torch can clone any flame, and receives its torch back after each cloning operation, in a state that allows it to continue cloning. More precisely, our correctness guarantee requires that a single torch can be used to clone a flame polynomially many times in succession, and that all the resulting flames pass verification with overwhelming probability. We require two security properties of a torch-fire scheme. The first is untelegraphability, which we require to hold even against parties that hold torches. That is, two parties that do not share any entanglement (but may share classical randomness), each possibly holding its own set of torches, cannot use classical communication to transmit a flame from one to the other. The second property, which is our main focus, is global non-proliferation. Here, an adversary receives a set of m torches of its choice, together with polynomially many flames, and may process all of these jointly. It then distributes arbitrarily entangled registers among N parties, after which the parties may no longer communicate. Each party now receives a fresh challenge flame, issued independently, and attempts to output two flames that both verify under the serial number of its challenge. Global non-proliferation requires that, except with negligible probability, at most m of the parties succeed. Theorem 1.2 (Informal). Relative to classical oracles, there exists a torch-fire scheme satisfying correctness, untelegraphability (even against parties holding torches), and global non-proliferation. That is, for any polynomial N and any m ≤ R, no efficient adversary given m torches can enable more than m noncommunicating parties to each clone a fresh challenge flame, except with negligible probability. Setting m = 0, global non-proliferation in particular implies that flames are uncloneable (in the functional sense) for parties that do not hold any torch. Further, it implies that torches cannot be cloned or split in any functional sense either: with m torches, cloning remains possible from at most m locations, regardless of how the torches are processed or entangled across these locations. We note that this guarantee is quite different from the usual uncloneability of the torch states themselves. Indeed, it is not about whether an adversary can produce copies of a torch, but whether it can distribute the capability to clone among more parties than it was given torches. We also remark that Theorem 1.2 holds unconditionally relative to classical oracles. Following [ÇGS26], we work in a model where each instance of the scheme is associated with its own sampled collection of classical oracles. For our case also we can lift it to the standard oracle model where there is one global oracle and the setup procedure samples public key, secret key to specify the corresponding oracles. Our construction. A torch in our scheme is simply the signing state of a (long-message) oneshot signature scheme [SZ25]. A flame consists of a flame of the quantum fire scheme of [ÇGS26], together with an independently generated one-shot signing state that we call its anchor, which is what makes flames uncloneable to parties without a torch. Cloning the anchor requires access to an oracle that answers only when queried with valid signatures from both the anchor and a torch, all computed coherently and then uncomputed, so that the torch is left essentially undisturbed and can be reused. Untelegraphability is inherited from the scheme of [ÇGS26]. We give an overview of the construction in Section 2.3. 5

Extraction from separated computations. The main technical challenge lies in proving global non-proliferation. Roughly, a party that clones its challenge flame must have obtained answers from the anchor-cloning oracle for that flame, and so must have produced a valid torch signature on a message involving that flame. Extracting such signatures from m + 1 successful parties, using only m torches, would then contradict the security of the one-shot signature scheme. The difficulty is that the parties share an arbitrarily entangled state, so the events of successful cloning at different locations, as well as the outcomes of any local extraction procedures, may be arbitrarily correlated. We need that whenever at least m + 1 parties succeed, local procedures that do not communicate with each other simultaneously extract at at least m + 1 locations. To this end, we prove a general extraction lemma for N separated oracle computations run on an arbitrary (possibly entangled) joint input. Consider modifying the oracle on some set of inputs, which we call witnesses. Our lemma states, roughly, that the probability that at least d of the original computations accept is at most the probability that at least d efficient local extractors each output a witness, plus an error term. This error term is governed by the probability that the modified computations accept after their inputs have been passed through a suitable filter, along with quantities that can be made arbitrarily (inverse-polynomially) small through the choice of parameters. We believe that this lemma may be of independent interest, and anticipate that it will find more applications in settings involving several non-communicating parties that share entanglement. We describe the lemma and its application in Section 2.4. Open questions. Our work leaves several natural questions open. Both of our constructions are in the classical oracle model, and it would be interesting to instantiate them in the standard model, for instance building on the approach of [CNS26]. It would also be interesting to achieve a publicly verifiable variant of our first construction, or to support an unbounded number of cloning generations with a classical key. For torch-fire, our untelegraphability guarantee is against parties that do not share entanglement and communicate classically; a stronger notion would allow arbitrary LOCC protocols between the parties. Finally, a very pertinent question is to study whether one can realize quantum key-fire with delegatable cloning properties. This seems to require nontrivial additions to our approach. Organization. We give the overviews behind our technical results in Section 2. Section 3 describes several preliminaries of quantum information and computation used in this paper. In Section 4, we describe the two foundational cryptographic building blocks: One-shot Signature due to [SZ25] and Quantum Fire due to [ÇGS26] and their underlying machinery used in our approach. In, Section 5, we give the construction of the delegatable quantum fire in the classical secret key realm. In Section 6, we formally define the torch-fire primitive ans especially its global non-proliferation property. In Section 7, we give a construction of the torch-fire object and prove its correctness and untelegraphability properties. In Section 8, we develop the extraction lemma and using it prove the global non proliferation property of the torch-fire object.

1.2

Related Work

Quantum fire and no-telegraphing. The notion of quantum fire was introduced by Nehoran and Zhandry [NZ24], who used it to separate no-cloning from no-telegraphing relative to a quantum oracle, and also separated cloneableQMA from QCMA in the same setting. Bostanci, Nehoran, and Zhandry [BNZ25] gave a general duality theorem for representations of groups, with applications to quantum money, lightning and fire, along with a candidate construction of quantum fire from

6

group actions. The work of Çakan, Goyal, and Shmueli [ÇGS26] gave the first construction of public-key quantum fire relative to classical oracles, along with quantum key-fire, and our torchfire construction uses their scheme as a building block. We note that key-fire is quite different from what we consider here: there, the flame itself is a functional key that anyone may clone, whereas in our setting, cloning is the capability being restricted. Casper, Nehoran, and Sattath [CNS26] gave the first standard-model construction of quantum fire, assuming one-shot signatures along with indistinguishability obfuscation and LWE, and our first construction follows their template. In a related direction, untelegraphable encryption, where an adversary is restricted to holding classical information about a ciphertext, was introduced by Champion, Kitagawa, Nishimaki, and Yamakawa [CKNY25], and further studied by Broadbent, Culf, and Rochette [BCR26]. Security against classical leakage of quantum states has also been studied by Çakan, Goyal, Liu-Zhang, and Ribeiro [ÇGLR24]. One-shot signatures. One-shot signatures were introduced by Amos, Georgiou, Kiayias, and Zhandry [AGKZ20]. Shmueli and Zhandry [SZ25] gave a construction relative to classical oracles with unconditional security, which forms the basis of both of our constructions. A simpler and more efficient construction was subsequently given by Huang and Vaikuntanathan [HV25], with further improvements by Huang, Shmueli, Vaikuntanathan, and Zhandry [HSVZ26]. Bartusek, Gupte, Mutreja, and Shmueli [BGMS25a] showed that the scheme of [SZ25] satisfies a delayed collapsing property, which is central to the analysis of our first construction. In a sense, our torches can be seen as one-shot signing states that are used repeatedly, but only in superposition, and are never measured. Delegating and revoking quantum capabilities. The idea of granting a limited capability through a quantum state also appears in quantum tokens for digital signatures [BS23], where a token permits a single signature, and in secure software leasing [AL21] and secure key leasing [KN22; AKNYY23; APV23], where a program or key can be lent out and later verifiably returned. In these settings, the capability is either consumed upon use or meant to be revoked. In contrast, our torches can be used an unbounded polynomial number of times, and the guarantee we seek is that the capability they confer cannot be spread to more locations than there are torches. Extraction against entangled parties. Arguing about several non-communicating parties that share entanglement is a recurring challenge in uncloneable cryptography, for instance in the analysis of monogamy-of-entanglement games [TFKW13]. In the oracle setting, Broadbent and Lord [BL20] proved a simultaneous version of the one-way-to-hiding lemma [Unr15; AHU19] for two entangled parties, whose loss was shown by Majenz, Schaffner, and Tahmasbi [MST21] to be inherent to some extent, and two-party simultaneous extraction from oracle queries was further developed in [CMP24; AKLLZ22]. Simultaneous reductions for two parties also appear in [AKY25; CLX26], and collusion-resistant copy-protection and multi-copy uncloneable primitives [LLQZ22; ÇG24] handle k + 1 entangled parties that must all succeed, using projective implementations [Zha20]. Simultaneous extraction from several extractors acting on a common state also arises in the context of post-quantum non-malleability [CLPY25]. Our extraction lemma differs from these in handling threshold events over any polynomial number of separated locations, and in extracting oracle queries using only local, efficient procedures. Its proof uses the alternating projector technique of Marriott and Watrous [MW05], which has been used extensively for extraction from quantum adversaries [Zha20; CMSZ21; LMS22], together with a hybrid argument along the lines of [BBBV97]. We give a more detailed comparison in Section 2.4. 7

Statements on AI usage: Generative AI assistants (Claude Fable 5.1 and ChatGPT Astra 6) were used extensively for writing and editorial changes. Additionally, ChatGPT 6 Astra Pro helped suggest the final torch fire construction (based on heuristics the authors already had) as well as an initial proof sketch, which was significantly cleaned up and redesigned. The problem motivation, framing and the broad approach are solely the authors’ work. LLMs were also used for literature search. The authors verified the technical and editorials contents generated by AI tools and take full responsibility for them.

2

Technical Overview

This section provides an overview of our techniques. We first recall the one-shot signature scheme of [SZ25], which underlies both of our constructions, in Section 2.1. We then discuss our construction with a classical secret key in Section 2.2. After that, we describe our torch-fire construction in Section 2.3, and the proof of global non-proliferation, including our extraction lemma, in Section 2.4.

2.1

One-Shot Signatures in the Classical Oracle Model

We briefly recall the one-bit one-shot signature scheme of Shmueli and Zhandry [SZ25], ignoring the specific parameters. The scheme is defined relative to a uniformly random permutation π on n-bit strings, whose output is split as π ( x ) = ( H ( x ), J ( x )), together with a uniformly random fullrank matrix Ay and a shift by for every y in the range of H. These define, for every y, a coset Wy = by + colspan( Ay ). The public oracles are as follows: a forward oracle P( x ) = ( H ( x ), A H (x) J ( x ) + b H (x) ), its inverse P−1 , which in particular reveals whether a string u lies in Wy , and a dual oracle D (y, v), which tests whether v lies in the dual of the subspace colspan( Ay ). None of the matrices, shifts, or the permutation are disclosed beyond these oracles. Applying P to a uniform superposition of inputs and uncomputing the input using P−1 gives a superposition ∑y |y⟩ |Wy ⟩, where |Wy ⟩ is the uniform superposition over Wy . Measuring the first register then gives a uniformly verification key y, and the signing state |Wy ⟩. A signature on a bit b is any element of Wy whose first bit is b, which can be checked using P−1 . To sign, one measures the first qubit of |Wy ⟩, and if the ‘wrong’ bit is measured, uses the dual oracle D (in the Hadamard basis) to restore the state to a uniform superposition over Wy before trying again. Multiple bits are signed using parallel instances 1 Briefly, security says that no efficient adversary can produce valid signatures on two distinct messages (or, in the strong version, two distinct message-signature pairs) under the same verification key, even with access to all three oracles. Two features of this scheme are central to our constructions. First, the dual oracle D is needed for signing, but not for generating keys or verifying signatures. Second, the projector onto the signing state |Wy ⟩ itself can be measured publicly: one tests membership in Wy using P−1 , then applies Hadamards and tests membership in the dual subspace using D. Two registers that both pass this test can be measured to obtain two independent uniformly random elements of Wy , which are distinct with overwhelming probability, and so give a strong one-shot signature forgery. This is the precise sense in which signing states are uncloneable. 1 For efficiency,

long messages are first hashed using a random oracle. known [HV25; HSVZ26]; we do not rely on them here.

8

More efficient multi-bit schemes are

2.2

Delegation via a Classical Secret Key

Withholding the dual oracle. Our first construction relies on the first observation above, namely that if the dual oracle D of [SZ25] is withheld from the public, then a party that holds a signing state |Wy ⟩ but only has access to P and P−1 can still verify signatures and check coset membership, but cannot sign arbitrary messages. In other words, signing becomes an operation that requires a specific authorization, namely (access to) D. We would like to use this property to make cloning a keyed operation for our purposes. However, a signing state itself cannot simply be copied, even with D, and so we look towards a notion of flames for which “cloning” means producing two new states that each pass verification, rather than two copies of a pristine signing state. Flames as signature chains. A quantum fire construction along these lines was recently obtained by Casper, Nehoran, and Sattath [CNS26]. Following their approach, we let a flame state consist of a current one-shot key pair together with a chain of signatures certifying its provenance. During spark, the authority samples the oracles ( P, P−1 , D ) and a root key pair (pkroot , |sk⟩), and sets the serial number to consist of pkroot (along with the public oracles). The initial flame is (∅, pkroot , |sk⟩), and the secret key is D. To clone a flame (hist, pkcur , |skcur ⟩), one generates two fresh key pairs (pk0 , |sk0 ⟩) and (pk1 , |sk1 ⟩) using only the public oracles, and then uses D and the current signing state to sign the message pk0 ∥pk1 , obtaining a signature σ. The two children are

hist∥(pk0 , pk1 , σ ), pk0 , |sk0 ⟩ and hist∥(pk0 , pk1 , σ ), pk1 , |sk1 ⟩ . The original signing state is consumed in this process, which is consistent with the requirement that the parent flame produces exactly two clones - in this case it is replaced by its children. To verify a flame, one checks that every entry in its history is a valid signature on the next pair of keys, under one of the two keys of the previous entry (starting from pkroot ), that the current key is one of the two keys in the last entry, and that the current signing state passes the projective test for |Wpkcur ⟩ described above. Since this last test uses D, verification is also private. Verification additionally rejects histories longer than a fixed bound c(λ), and reports the number of remaining clones c(λ) − T for a flame with history of length T. Correctness of verification and cloning follows from the correctness of the one-shot signature scheme. As in [CNS26], we also require the depth of the flame state to be bounded by c(λ) = O(log λ) in order to obtain an efficient reduction from OSS security to untelegraphability. The reason for this is because the reduction must compute all possible continuations of the flame state. Uncloneability without the key. Consider an adversary that is given a flame (possibly after some honest cloning operations) and access only to P and P−1 , and outputs two registers that both pass verification. We first observe that it suffices to bound the adversary’s success when the projective test on the current signing state is replaced by a weaker coset test, which simply measures the register and checks membership in Wpkcur using P−1 . Any state that passes the original test passes the coset test with at least the same probability, so this replacement can only help the adversary. The advantage is that the entire remaining experiment, namely the adversary and the modified verification, now only uses P and P−1 . This allows us to use the delayed collapsing property of the scheme of [SZ25], recently established by Bartusek, Gupte, Mutreja, and Shmueli [BGMS25a]. Roughly, this says that a register that (when measured) yields a valid signature cannot be distinguished from its measured version by any efficient procedure that only has access to P and P−1 , even if the register itself was prepared using all three oracles. This is precisely our setting: the adversary’s flame may be the 9

result of honest cloning operations performed using D, but everything after that point avoids D. We may therefore move, through a sequence of hybrids, to an experiment where each single-bit signing state held by the adversary has been measured in the computational basis. We note that ordinary collapsing would not suffice here, since the honest preparation of the flame requires D. In the fully collapsed experiment, we can reduce to the security of the one-shot signature scheme. The key observation is that a measured signing state, i.e., a uniformly random element of Wy , is distributed identically to a signature on a uniformly random bit. Since the concatenation of two freshly generated verification keys is itself uniformly random, for each (measured) signing state given to the adversary, the reduction can sample the next generation of keys (pk0 , pk1 ) in advance, retaining their signing states, sign pk0 ∥pk1 using the signing state (and the dual oracle, which it has in the one-shot signature security game), and give the resulting signature to the adversary in place of the measured signing state. The adversary’s view is identical to that in the collapsed experiment. Now suppose the adversary outputs an accepted flame that extends the b 0 , pk b 1 , σ̂ ). If pk b 0 ∥pk b 1 ̸= pk0 ∥pk1 , then the two messages differ in some bit, chain by a new entry (pk and the corresponding components of σ̂ and the reduction’s signature give valid signatures on two distinct bits under the same single-bit key. Otherwise, the adversary’s flame contains a state that passes the coset test for one of the keys pka that the reduction generated, and whose signing state the reduction still holds. Measuring a component of the adversary’s state gives a signature on some bit b, and the reduction can use its own signing state to sign 1 − b. In both cases, this violates the security of the one-shot signature scheme. Note that in the case where the adversary outputs a clone where the new pk0 = pk1 = y, the reduction is significantly simpler. In this case, the corresponding state in the signing key register of both clones is the OSS signing key corresponding to y. Therefore, the adversary can use the two copies of the keys to sign different bits and violate OSS security. Untelegraphability. The argument for untelegraphability follows the reduction to OSS security presented in [CNS26] almost verbatim. We briefly outline it here. Suppose QPT adversaries A A and B B share a classical channel and A is able to telegraph a flame state to B. Recall that the depth of the flame state is bounded by c log(λ). Therefore, the reduction makes A A telegraph the flame state to B more than 2c log(λ) many times. By the pigeonhole principle, we must have that either 2 of the clones must terminate with the same public key, in which case the signing keys at the end of the chain in both clones can be used to violate OSS security. The other case is when a terminal public key in one clone coincides with a public key in the internal history of the other clone. Then we can again use the terminal signing key in the first clone to obtain an OSS forgery.

2.3

Torch-Fire

We now turn to torch-fire. Recall that we would like flames to be publicly verifiable, as well as cloneable by any party holding one of the R torches issued at setup but uncloneable (functionally) for everyone else, and untelegraphable even for parties holding torches. Moreover, we would like global non-proliferation: m torches should enable cloning at no more than m separate locations. Starting point: CGS fire. Our starting point is the public-key quantum fire scheme of Çakan, Goyal, and Shmueli [ÇGS26], which we refer to as CGS fire. A CGS flame is the state |K ⟩ = ∑y |y⟩ |Wy ⟩, i.e., the superposition over all verification keys and signing states of a one-shot signature instance, before measuring the key. The authority holds private access to a generation oracle G that bundles the forward, inverse and dual oracles of this instance. Public access to G is

10

provided through an oracle that answers a query z only when it is accompanied by a valid tag, consisting of a key y and two hash values of (y, z). These hash values are in turn only released in exchange for valid one-shot signatures on 0 and on 1 respectively under y. A party holding |K ⟩ can compute such a tag coherently, controlled on the key register, by signing both bits, querying the hash oracles, and uncomputing the signatures. Since honest signatures are accepted with overwhelming probability, this disturbs |K ⟩ only negligibly. Thus a holder of a CGS flame can query G, and in particular can run the preparation circuit for |K ⟩ on fresh registers, which gives public cloning. [ÇGS26] also show that the resulting scheme is untelegraphable. Anchors. To restrict cloning, one could try to modify CGS fire directly, for instance by requiring additional credentials in its public oracles. We instead leave the CGS fire state intact (so that we can use its untelegraphability as is) and attach to each flame a second component whose uncloneability is easy to reason about. We call this the anchor: an independently generated signing state | A a ⟩ = N c |Wac ⟩ of a (L-bit) one-shot signature scheme, with verification key a = ( a1 , . . . , a L ). The flame state is thus | A a ⟩ ⊗ |K ⟩, and it is verified by applying the projective test for | A a ⟩ from Section 2.1 to the anchor (componentwise) and running CGS verification on the second part. Since the accepting projector for the anchor is the rank-one projector | A a ⟩⟨ A a |, two registers that both pass anchor verification yield a strong one-shot signature forgery, exactly as described in Section 2.1. The anchors of different flames do not all use the same one-shot signature oracles. Instead, each flame has a uniformly random label ℓ ∈ {0, 1}λ , and its anchor is generated relative to an independent oracle collection O A,ℓ associated with this label. The serial number of the flame is s = (ℓ, a). This choice plays an important role in the proof of global non-proliferation, where we will need to disable access related to a single flame without affecting any other flame. Torches and cloning anchors. A torch is also a signing state | Tt ⟩ of a multi-bit one-shot signature scheme (relative to a single oracle collection O T shared by all torches), with the verification keys t1 , . . . , t R of all issued torches published through a public oracle. Since we need torches for specific published keys, the authority receives the matrices and shifts defining the corresponding cosets, which allows it to prepare | Tt j ⟩ directly. To clone a flame with serial s = (ℓ, a), one clones its CGS part using the public cloning procedure of [ÇGS26], and must additionally prepare a fresh copy of |Wac ⟩ for every component c of the anchor. Unlike in the key generation procedure of [SZ25], the key ac here is fixed in advance, and so this cannot be done using the public oracles of O A,ℓ . Instead, we observe that |Wy ⟩ can be prepared from the two affine maps ( w if u = Ay w + by , affiney,0 (w) = Ay w + by , affiney,1 (u) = ⊥ if u ∈ / Wy , by preparing a uniform superposition over w, computing Ay w + by into a second register, and uncomputing w using the inverse map. These maps are never made available directly. Access to them is provided only through a dedicated public oracle Γ, which takes as input a query q = (s, t, c, e, u) asking for affineac ,e (u) in component c of the anchor source O A,ℓ , and answers only if all of the following hold: • t is the published key of an issued torch; • the query carries a valid anchor signature, under a, on the message 0∥⟨s, t⟩; • the query carries a valid torch signature, under t, on the message 1∥⟨s, t⟩; 11

• the query carries a valid CGS tag for (an encoding of) the query q itself. Here ⟨s, t⟩ = ℓ∥ a∥t, and the leading bit separates anchor and torch messages. In particular, every answered query is bound to the label ℓ of the flame being cloned and to the specific torch being used. Reusing the torch. The cloning procedure makes 2L queries to Γ, and each of them uses the same anchor, torch, and CGS flame. For each query, the party coherently computes the request, the CGS tag (using the CGS part of the flame, as in [ÇGS26]), and the two signatures (using the coherent signing circuits for the anchor and the torch), queries Γ, and then uncomputes everything except the answer. No signature, tag, or answer is ever measured. Since honestly computed signatures and tags pass the checks of Γ except with negligible probability, and Γ agrees with the ideal affine map whenever its checks pass, √ each such query acts as the ideal affine query on the honest resources, up to an error of 2 d in Euclidean norm, where d is the total signing and tagging error. In particular, the anchor, the torch and the CGS flame are returned essentially undisturbed. A hybrid argument over the 2L queries shows that a single cloning call produces a state that is negligibly close (in trace distance) to the torch together with two copies of the honest flame, and a further hybrid over polynomially many calls shows that a single torch can be reused to clone polynomially many times. This is what distinguishes torches from ordinary one-shot signing states: a torch is only ever used to sign in superposition, and is never measured. Untelegraphability. Untelegraphability reduces to that of CGS fire. Since the accepting effect for a flame is | A a ⟩⟨ A a | ⊗ B, where B is the accepting effect of CGS verification, it is dominated by I ⊗ B, and so it suffices to show that the adversary cannot telegraph the CGS part of a flame. Given a pair of telegraphing adversaries for torch-fire, we construct a pair for CGS fire as follows. The two reductions use shared classical randomness (which is allowed in the definition) to sample all torch and anchor oracles consistently, prepare the torches requested by each party locally, and forward all queries to the CGS oracles to the CGS challenger. Fresh flames are obtained by requesting a CGS flame from the challenger and attaching a freshly generated anchor. The only oracle that combines CGS data with the sampled data is Γ, through its tag check. Since Γ only checks tags on forward queries, for which the generation oracle never returns ⊥, a tag is valid exactly when the public CGS oracle answers the corresponding query. Thus each query to Γ can be simulated exactly using two queries to the public CGS interface, and the receiving reduction simply discards the anchor of its output flame.

2.4

Global Non-Proliferation

We now describe the proof of global non-proliferation. Recall that the adversary jointly processes m torches and polynomially many flames, splits into N non-communicating parties sharing an arbitrary entangled state, and each party i receives a fresh challenge flame with serial si = (ℓi , ai ) and attempts to output two flames that both verify under si . We first move to an experiment where all labels issued during the experiment are distinct, which only changes the success probability negligibly. The high-level idea. Fix a location i. If party i outputs two accepted flames, it must have produced two registers passing the anchor test for ai . Without any affine access to the anchor source O A,ℓi , this is impossible, as it would yield a one-shot signature forgery. So party i must have made queries to Γ on label ℓi , and any such query that Γ answers carries a valid torch signature on a 12

message beginning with 1∥ℓi . If we could extract such a torch signature from each of m + 1 successful parties, we would obtain m + 1 valid torch signatures on distinct messages (since the labels are distinct), while only m torches were issued. Then either two of these signatures are under the same issued torch, or one of them is under a torch that was never issued, whose signing state the reduction still holds and can use to sign a different message (say, one beginning with 0). Either way, this gives a forgery for the long-message one-shot signature scheme underlying the torches. The difficulty lies in the extraction step. The parties share an arbitrarily entangled state, and so the events of successful cloning at different locations may be arbitrarily correlated, as may the outcomes of any extraction procedures we run locally. It does not suffice to show that each successful party can individually be made to yield a torch signature. We need that whenever at least m + 1 parties succeed, local extraction procedures, which do not communicate with each other, simultaneously succeed at at least m + 1 locations. Moreover, we need this extraction to be efficient, since it is used inside a reduction to one-shot signature security. Original and modified computations. We formalize the above as follows. At location i, let Ui1 denote the (purified) computation that runs party i on its input register and then verifies both of its output flames under si , and let Πi project onto acceptance. We define a modified computation Ui0 that is identical, except that it uses a modified oracle Γ0i , which returns ⊥ on every query carrying the label ℓi . The two oracles only differ on queries that carry the label ℓi and are answered by Γ, and every such query carries a valid torch signature on a message involving ℓi . We therefore let the witnesses at location i be queries to Γ that carry label ℓi , an issued torch key t, and a valid torch signature under t. Notably, this predicate only checks the torch signature, and not the anchor signature or the CGS tag, so it can be tested using public oracles alone. The anchor key within the query also need not equal ai : only the label matters. An extraction lemma for separated computations. We abstract this situation into a general lemma. Consider N locations, each running a q-query oracle computation on its share of a joint (possibly entangled) input state ρ, in an original and a modified version that differ only on witness queries. Let Ai and Ci denote the accepting maps of the original and modified computations at location i. Let Ei be the effect corresponding to the following witness sampler: choose j ∈ [q] uniformly, run the modified computation up to its j-th query, and test whether the query is a witness. A standard hybrid argument in the style of [BBBV97], as in the proof of the one-way-to-hiding lemma [Unr15; AHU19], gives the operator inequality

( Ai − Ci )† ( Ai − Ci ) ⪯ 4q2 Ei , i.e., the original and modified computations can only differ substantially on components of the input on which the witness sampler succeeds with noticeable probability. We handle the two kinds of components separately. On components where the witness sampler rarely succeeds, we would like to replace the original computation by the modified one. To this end, we use the filter Li = ( I − Ei ) β , for a parameter β. This can be implemented efficiently as follows. We prepare a uniform superposition over j ∈ [q], coherently run the modified computation up to query j, perform the witness test and continue only on rejection, uncompute, and continue only if all ancillary registers are returned to zero. A successful run of this cycle applies exactly I − Ei to the input, and β successful runs apply Li . On the filtered input, the comparison above improves to Li ( Ai − Ci )† ( Ai − Ci ) Li ⪯ 4q2 Ei ( I − Ei )2β ⪯ 13

4q2 , 2β + 1

since the function u(1 − u)2β is at most 1/(2β + 1) on [0, 1]. Thus, after filtering, original acceptance is bounded by (twice) modified acceptance, up to an error that decreases with β. On components where the witness sampler often succeeds, we would like to actually extract a witness. Here we use an alternating projector procedure following Marriott and Watrous [MW05]. We run the coherent witness sampler once and test for a witness; if this fails, we alternate between measuring the projector onto the image of the (isometric) coherent sampler, and testing for a witness again, for t = ⌈2β/δ2 ⌉ rounds. On an eigenvector of Ei with eigenvalue u, the two projectors act on a two-dimensional invariant subspace, and each additional round succeeds with probability exactly 2u(1 − u), independently of previous rounds. A short calculation then shows that the success effect Wi of this extractor satisfies Wi ⪰ ( I − Li )2 − δI, by considering separately eigenvalues u ≥ δ/(2β), where the extractor succeeds with probability at least 1 − δ, and u < δ/(2β), where (1 − (1 − u) β )2 ≤ δ. Combining the two cases using the decomposition Ai = Ai ( I − Li ) + Ai Li and a weighted Cauchy–Schwarz inequality, we obtain a local comparison of the form Ai† Ai − Wi ⪯ δ(2 + δ) I + (1 + δ−1 ) Li Ai† Ai Li , where the last term corresponds to successful filtering followed by original acceptance, and is bounded in terms of modified acceptance as above. It remains to lift these local comparisons to a comparison between the events “at least d locations accept” and “at least d locations extract a witness”. Each of these events corresponds to a threshold effect, obtained by summing tensor products of local success and failure effects over all outcomes with at least d successes. We replace the acceptance effect by the extraction effect one location at a time. Changing the outcome at location i only affects the threshold event when exactly d − 1 of the other locations succeed, and so the difference between consecutive hybrids is exactly ( Ai† Ai − Wi ) ⊗ Gi , where Gi is the (positive semidefinite) effect of exactly d − 1 successes elsewhere. Since tensoring with a positive semidefinite operator preserves operator inequalities, the local comparison applies directly. This is what allows us to handle arbitrary entanglement between the locations without assuming any independence. Altogether, we obtain: Lemma 2.1 (Extraction from separated computations, informal). For any β, δ and threshold d, there are efficient local extractors such that h i h i   8Nq2 Pr ∑i Xi ≥ d ≤ Pr ∑i Yi ≥ d + Nδ(2 + δ) + (1 + δ−1 ) 2ε β + 2β+1 , where Xi and Yi indicate acceptance by the original computation and successful witness extraction at location i, and ε β is the total probability, summed over locations, that the filter Li succeeds and the modified computation then accepts. Comparison with prior techniques. The individual ingredients of Lemma 2.1 are standard. The operator inequality comparing the two computations is the operator form of the hybrid argument underlying the one-way-to-hiding lemma [BBBV97; Unr15; AHU19], and our extractor is an instance of the alternating projector technique of Marriott and Watrous [MW05], which has been used extensively for extraction and estimation against quantum adversaries [Zha20; CMSZ21; LMS22]. The filter Li is a polynomial in the witness-sampling effect Ei , implemented through postselection; we note that this is different from the measure-rewind-measure technique of [KSSSS20], which rewinds the final measurement of a distinguisher to extract from it. 14

What we are not aware of is a statement of this form for many entangled locations. The closest analogue is the simultaneous one-way-to-hiding lemma of Broadbent and Lord [BL20], which considers two non-communicating parties with shared entanglement that both query a random oracle, and bounds the probability that both of them guess the value of the oracle at a hidden point. The bound is in terms of the probability that measuring a uniformly random query of each party simultaneously reveals the hidden point, and incurs a constant multiplicative loss that Majenz, Schaffner, and Tahmasbi [MST21] showed cannot be reduced below 9/8. Coladangelo, Majenz, and Poremba [CMP24] gave a (lossy) two-party search-to-decision reduction of this kind for copy-protection in the quantum random oracle model, and Ananth, Kaleoglu, Li, Liu, and Zhandry [AKLLZ22] extracted from two entangled parties by combining Jordan’s lemma, a threshold measurement on each party, and measuring a random query. Related simultaneous statements for two parties, which do not involve oracle queries, include the simultaneous quantum Goldreich-Levin reductions of [AKY25; CLX26]. On the other hand, works on collusionresistant copy-protection and multi-copy uncloneable cryptography [LLQZ22; ÇG24] handle k + 1 entangled parties, and show that they cannot all succeed when given k copies, by applying projective implementations [Zha20] at each location and using the pigeonhole principle; these do not involve extracting oracle queries. Our own earlier simultaneous extraction lemma [CLPY25] considers several extractors acting on the same quantum state, each with a unique output, rather than separated computations. In comparison, Lemma 2.1 applies to any polynomial number N of separated locations, and directly compares the threshold events “at least d of N locations accept” and “at least d of N locations extract”. This is important for our application, since the adversary may distribute its resources among N ≫ m + 1 parties, and we do not know in advance which m + 1 of them succeed. A naive approach that guesses a set of m + 1 locations and applies a simultaneous extraction argument to it would lose a factor of (mN+1), which is superpolynomial in general (for instance, when N = 2m and m grows with λ). Moreover, the error in our lemma is not bounded in terms of a finding probability; it is instead expressed through the acceptance probability of the modified computations after filtering, which we bound through a separate reduction (in our case, to the security of the anchors). Bounding filtered modified acceptance. To apply Lemma 2.1, we first show that ε β is negligible for any polynomial β, using the security of the one-shot signature scheme underlying the anchors. The idea is that in the modified computation at location i, no query on label ℓi is ever answered, so the reduction can embed a one-shot signature challenge into the anchor source O A,ℓi (specifically, into its first component) without ever needing the corresponding affine maps. The reduction guesses the location i uniformly at random, samples all other oracles itself, and generates the first component of the challenge anchor ai using the public key generation procedure of the challenge oracles. It then runs the filter followed by the modified computation at location i, and on acceptance, measures the first component of both accepted anchors. Since both anchors were projected onto | A ai ⟩, this gives two independent uniform elements of the challenge coset, and hence two distinct signatures under the challenge key, with overwhelming probability. Note that the reduction can implement the filter, since witnesses are testable using public torch verification. There is one subtlety. The joint input ρ was prepared before the split using the original oracle Γ, and so may already contain information obtained from affine queries on label ℓi , which the reduction cannot answer. We therefore also disable these queries before the split. This only changes the input state negligibly, since the challenge label ℓi is uniformly random and unknown to the adversary at that point. Concretely, the total query mass on a uniformly random label is at most

15

Qpre 2−λ in expectation for Qpre pre-split queries, and the hybrid argument of [BBBV97] bounds the resulting change by 2Qpre 2−λ/2 . Bounding extraction. Next, we show that witnesses for m + 1 distinct labels can only be obtained with negligible probability, using the security of the long-message one-shot signature scheme underlying the torches. The reduction embeds the challenge oracles as the torch source O T , and generates all R torches itself using the public key generation procedure. This gives the correct distribution of torches without the authority’s private data. It hands the m requested torches to the adversary and retains the rest, and samples the anchor and CGS sources itself, so that it can answer all affine queries and tag checks. The challenge oracles are only needed for torch verification within Γ. As discussed above, m + 1 witnesses on distinct labels yield either two signatures on distinct messages under the same issued torch, or a signature under an unissued torch, which the reduction can combine with its own signature (computed using the retained torch) on a message beginning with 0. Putting things together. Combining the two bounds with Lemma 2.1 at threshold d = m + 1, we obtain that the probability that at least m + 1 parties succeed is at most negl(λ) + Nδ(2 + δ) + (1 + δ−1 )

8Nq2 . 2β + 1

For any constant c, choosing δ = 1/(2Nλc ) and β = ⌈ N 2 q2 λ2c ⌉ keeps the extractors and the filter efficient, and makes this bound O(λ−c ). Since the success probability does not depend on these parameters, and c is arbitrary, it must be negligible.

3

Preliminaries

Basic Notations. We write N0 = {0, 1, 2, . . .}. For n ∈ N, let [n] = {1, . . . , n}. Given a finite set S, we use |S| to denote its cardinality and x ← S to denote uniform sampling from S. For a statement E , its indicator 1[E ] is 1 if E holds and 0 otherwise. We use λ for the security parameter. A function ϵ(λ) is negligible if, for every polynomial p(λ), we have ϵ(λ) < 1/p(λ) for all sufficiently large λ. We write negl(λ) for an unspecified negligible function. Notations for Quantum Computing. We use the standard finite-dimensional quantum formalism as in [NC00]. For a vector |ψ⟩ in a Hilbert space H, ⟨ψ| denotes its conjugate transpose, ⟨ϕ|ψ⟩ denotes the inner product, and |ϕ⟩ ⟨ψ| denotes the outer product. The norm ∥|ψ⟩∥ is the standard ℓ2 norm. For a d-dimensional Hilbert space, the computational basis is {|0⟩ , . . . , |d − 1⟩}. A quantum register F has an associated Hilbert space H F , and the joint space of registers F, G is H F ⊗ HG . We write IF for the identity operator on H F . Register subscripts and identity operators on untouched registers are omitted when clear from context. Positive Semidefinite Operators and Operator Order. For a linear operator A, let A† denote its adjoint. A Hermitian operator A is positive semidefinite (PSD), written A ⪰ 0, if ⟨v| A |v⟩ ≥ 0 for every vector |v⟩. Equivalently, all eigenvalues of A are nonnegative. For Hermitian operators A, B on the same space, we write A ⪯ B, or B ⪰ A, if B − A ⪰ 0. For every compatible linear operator C, A ⪯ B =⇒ C † AC ⪯ C † BC. 16

We will also use that, for T ⪰ 0 and ρ ⪰ 0, A⪯B

A ⊗ T ⪯ B ⊗ T,

=⇒

Tr( Aρ) ≤ Tr( Bρ).

Pure and Mixed States. A pure state is represented by a unit vector |ψ⟩, or equivalently by the density operator |ψ⟩⟨ψ|. A (possibly) mixed state of a register F is denoted by ρ F and is a unit trace PSD operator on H F . We also allow subnormalized states for the sake of analysis: PSD operators ρ satisfying Tr(ρ) ≤ 1. For a joint state ρ FG , its reduced state on F is ρ F = TrG (ρ FG ), where TrG denotes the partial trace over G. Projectors and Measurements. An orthogonal projector Π on H satisfies Π† = Π and Π2 = Π. Its support/range is Ran(Π) = {|v⟩ ∈ H : Π |v⟩ = |v⟩}. In particular, 0 ⪯ Π ⪯ I. A projective measurement is a collection of pairwise orthogonal projectors {Πi }i satisfying ∑i Πi = I. On input ρ, the probability of outcome i is pi = Tr(Πi ρ). For a pure input |ψ⟩⟨ψ|, this equals ∥Πi |ψ⟩∥2 . The unnormalized state after outcome i is Πi ρΠi ; if pi > 0, its normalized state is Πi ρΠi /pi . A computational-basis diagonal projector has the form ΠS = ∑ x∈S | x ⟩⟨ x | for a subset S of the computational-basis states. Measuring {ΠS , I − ΠS } tests membership in S. Quantum Effects. A quantum effect is an operator E satisfying 0 ⪯ E ⪯ I. It describes the acceptance probability of a quantum test: on input ρ, the test accepts with probability Tr( Eρ). For example, let V be an isometry, so that V † V = I, and let Π be an acceptance projector. Applying V and then testing Π has acceptance effect E = V † ΠV, 0 ⪯ E ⪯ V † V = I, and hence, by cyclicity of trace, Pr[accept] = Tr( Eρ) = Tr(ΠVρV † ) Operator Norms and Trace Distance

For a linear operator A : H → K, its spectral norm is

∥ A∥op =

∥ A |v⟩∥ .

sup |v⟩∈H : ∥|v⟩∥=1

We also write ∥ A∥ when the operator norm is clear from context. An operator A is a contraction if ∥ A∥op ≤ 1, equivalently A† A ⪯ I. The trace norm is defined √  as: ∥ A∥1 = Tr A† A . For density operators ρ, σ on the same space, their trace distance is D (ρ, σ ) = 12 ∥ρ − σ∥1 . Classical Oracles Queried in Superposition. For a classical function f : {0, 1} a → {0, 1}b , an oracle for that function query-able in superposition means access to the unitary x ∈ {0, 1} a ,

O f | x, z, w⟩ = | x, z ⊕ f ( x ), w⟩ ,

z ∈ {0, 1}b ,

where ⊕ denotes bitwise XOR and w labels the remaining workspace. The action on arbitrary superposition of states is determined by linearity. In particular, !

Of

∑ α x | x ⟩ | 0b ⟩ x

= ∑ α x | x ⟩ | f ( x )⟩ . x

The notation AO indicates that A has quantum query access to the specified collection O of classical functions. 17

Query-Bounded Quantum Algorithms. A T-query quantum algorithm acts on a query register Q, an answer register Z, and a working register W. Its computation can be written as U O = GT O T GT −1 · · · G1 O1 G0 , where G0 , . . . , GT are unitaries between queries and O j is the j-th query to the specified oracle collection. Quantum Polynomial-Time Algorithms. A quantum polynomial-time (QPT) algorithm is described by a uniformly generated family of quantum circuits whose size and number of qubits are polynomially bounded in the input length. For an oracle-aided algorithm, each oracle query counts as one gate; in particular, its total number of oracle queries is polynomially bounded. The oracle functions themselves need not be efficiently sampleable or evaluable. Fact 3.1. Let AO be an oracle aided QPT algorithm with classical input x ∈ {0, 1}n , quantum input register R, and classical output. The input and output register sizes are fixed polynomially bounded functions of n. The algorithm can perform any intermediate measurement and use classical randomness. Let the oracle O provides access to a classical function f : {0, 1} a → {0, 1}b through the unitary q ∈ {0, 1} a ,

O f |q⟩ |z⟩ = |q⟩ |z ⊕ f (q)⟩ ,

z ∈ {0, 1}b .

Then, there are polynomial-size registers E, C, and oracle aided QPT implementable unitaries UxO acting on the registers REC satisfying the following property. The register C holds the output, and E contains all auxiliary workspaces. For every density operator ρ R and every output c, h i h i Pr AO ( x, ρ R ) = c = Tr ( IRE ⊗ |c⟩⟨c|C ) UxO (ρ R ⊗ |0⟩⟨0| EC )(UxO )† .

(1)

This follows from reversible computation and the principle of deferred measurement; see [NC00]. Lemma 3.2 (BBBV hybrid bound [BBBV97]). Consider two executions b ∈ {0, 1} of a quantum algorithm with the same initial state and the same unitary operations between queries. The query input domain is D . The difference between the two executions is: at query j ∈ [q], execution b applies a query unitary Obj . For each j, let Pj be a projector on the query registers such that

(O1j − O0j )( I − Pj ) = 0. i.e., for every input | x ⟩ ∈ D lying outside the support of the projector Pj , both the oracle outputs are identical. Let ρ j be the state of the query input register immediately before query j in execution 1, and let σb be the final state of execution b. Define q

M := ∑ Tr( Pj ρ j ). j =1

Then D (σ1 , σ0 ) : =

p 1 1 σ − σ0 ≤ 2 qM. 2 1 18

4

Cryptographic Building Blocks

4.1

One-shot signatures (OSS)

We first start with the definition of One-shot Signature in a classical oracle model as introduced in [AGKZ20]. Definition 4.1. Let {Mλ }λ∈N be a family of classical message spaces of polynomially bounded message length. A one-shot signature scheme consists of an oracle-generation procedure and three QPT algorithms: OSS = (OSS.GenOracles, OSS.GenQKeyO , OSS.SignO , OSS.VerO ) 1. O ← OSS.GenOracles(1λ ): an oracle-generation procedure that samples a collection O of classical oracles. 2. (y, R) ← OSS.GenQKeyO (1λ ): a QPT algorithm that outputs a classical verification key y and a quantum signing register R. 3. σ ← OSS.SignO (y, R, m): a QPT algorithm that, on input a verification key y, a signing register R, and a message m ∈ Mλ , outputs a classical signature σ. 4. b ← OSS.VerO (y, m, σ ): a deterministic polynomial-time classical algorithm that outputs b ∈ {0, 1}. All the algorithms and adversaries have query access to the oracle O query-able in superposition. The scheme must satisfy the following properties. Correctness.

For every m ∈ Mλ ,  O ← OSS.GenOracles(1λ )  (y, R) ← OSS.GenQKeyO (1λ )   ≥ 1 − negl(λ). Pr b = 1 :   σ ← OSS.SignO (y, R, m) O b ← OSS.Ver (y, m, σ ) 

One-shot security.

(2)

For every quantum adversary A making polynomially many oracle queries,

 O ← OSS.GenOracles(1λ ) m ̸ = m1 ∧  ≤ negl(λ). Pr 0 : (y, m0 , σ0 , m1 , σ1 ) ← AO (1λ ) b0 = b1 = 1 O bi ← OSS.Ver (y, mi , σi ), i ∈ {0, 1} 

(3)

Strong one-shot security. The scheme satisfies strong one-shot security if (3) holds with the condition m0 ̸= m1 replaced by (m0 , σ0 ) ̸= (m1 , σ1 ). i.e., the underlying message may be the same but the produced signatures need to be distinct. All probabilities are taken over oracle sampling, the randomness of the algorithms, and measurement outcomes. Now, we shall describe the technical tools needed for the classical oracle OSS construction due to [SZ25] followed by the construction with the modifications done in [ÇGS26].

19

Construction 4.2 (Oracle distribution [SZ25, Construction 28]). For λ ≥ 2, set r = 16λ(λ − 1),

n = r + 24λ,

k = n.

(4)

Sample a uniform permutation π : {0, 1}n → {0, 1}n and write

| H ( x )| = r,

π ( x ) = ( H ( x ), J ( x )),

| J ( x )| = n − r. k ×(n−r )

Independently for each y ∈ {0, 1}r , sample a uniform full-rank matrix Ay ∈ Z2 form vector by ∈ Z2k . Define the subspace Sy and the coset Wy as follows: Sy = { Ay w : w ∈ Z2n−r },

Wy = by + Sy .

and a uni(5)

The public oracle collection is O = (P , P −1 , D), where

P ( x ) = ( H ( x ), A H ( x ) J ( x ) + b H ( x ) ), ( π −1 (y, w), u = Ay w + by for some w ∈ Z2n−r , P −1 (y, u) = ⊥, otherwise,

(6)

D(y, v) = 1[vT Ay = 0n−r ]. Fact 4.3. We note that, beyond the access to these oracles, none of the matrices, shifts, and permutation are publicly disclosed. Fact 4.4. Full column rank makes the inverse coordinate w unique. Consequently,

P −1 (P ( x )) = x,

P −1 (y, u) ̸=⊥ ⇐⇒ u ∈ Wy .

Definition 4.5. For each y, the corresponding coset superposition state is:

|Wy ⟩ = 2−(n−r)/2

∑ − | Ay w + by ⟩ = 2−(n−r)/2 ∑ |u⟩ .

w∈Z2n r

(7)

u∈Wy

The following procedure describes, how using the oracles P and P −1 , one can prepare the coset superposition states. Construction 4.6 (Coset Superposition State Preparation, [SZ25, Construction 31]). For registers X, Y, U of n, r, k qubits, respectively, we apply the following sequence of procedures in the the specified registers,

| 0 n ⟩ X | 0r ⟩ Y | 0 k ⟩ U H ⊗n

−−X→ 2−n/2 ∑ | x ⟩ X |0r ⟩Y |0k ⟩U x

Query P from X to YU

−−−−−−−−−−−−→ 2−n/2 ∑ | x ⟩ X | H ( x )⟩Y | A H (x) J ( x ) + b H (x) ⟩U x

Query P −1 from YU to X

−−−−−−−−−−−−−→ 2−n/2 ∑ |0n ⟩ X | H ( x )⟩Y | A H (x) J ( x ) + b H (x) ⟩U x

n

= |0 ⟩ X ⊗ 2

−n/2

= |0n ⟩ X ⊗ 2−r/2

∑

∑

y∈{0,1}r w∈Z2n−r

∑

y∈{0,1}r

| y ⟩Y | A y w + by ⟩ U

|y⟩Y |Wy ⟩U .

Measuring Y gives Pr[Y = y] = 2−r ,

and the state ρU |Y =y = |Wy ⟩⟨Wy | . 20

(8)

Construction 4.7 (One-bit signatures). Let the message space is {0, 1}. We use the signing algorithm to be the repeated trial algorithm of [ÇGS26, Section 6.2]. (i) OSS.GenOracles(1λ ): sample and return O = (P , P −1 , D) according to Construction 4.2. (ii) OSS.GenQKeyO (1λ ): execute Construction 4.6 and measure the register Y. Output (y, R), where the signing key R is taken to be the register U. Thus the verification key y is uniform on {0, 1}r and, corresponding to y, the signing key R is |Wy ⟩⟨Wy |. (iii) OSS.SignO (y, R, b): for j = 1, . . . , λ, execute: (a) Measure the first qubit of R in the computational basis, obtaining c. If c = b, measure the remaining qubits, obtaining u′ ∈ {0, 1}k−1 , and return u = b∥u′ . (b) If c ̸= b, apply H ⊗k to R and evaluate D(y, ·) into a fresh qubit:

|v⟩ R |0⟩ B 7−→ |v⟩ R |D(y, v)⟩ B . Measure the register B, apply H ⊗k to R, and continue to the next iteration. Return ⊥ if all λ attempts fail. (iv) OSS.VerO (y, b, u): Reject unless (y, b, u) ∈ {0, 1}r × {0, 1} × {0, 1}k . Otherwise output OSS.VerO (y, b, u) = 1[P −1 (y, u) ̸=⊥] ∧ 1[u1 = b].

(9)

The following is the affine-coset version of the standard hidden-subspace verification test of [AC12]. For, sake of completeness, We include a short proof in our notation. Lemma 4.8. Fix the oracles in Construction 4.2 and a verification key y. Consider the membership testing projectors Θy = ∑u∈Wy |u⟩⟨u| , Qy = ∑v∈Sy⊥ |v⟩⟨v| , and the procedure Q′y = H ⊗k Qy H ⊗k . Then, for every u ∈ Z2k ,

Q′y |u⟩ = 2−(n−r)

∑

|w⟩ .

(10)

Πy := Q′y Θy = |Wy ⟩⟨Wy | .

(11)

w ∈ u + Sy

Moreover,

Proof. The amplitude of |w⟩ in Q′y |u⟩ is 2−k ∑ (−1)

( vT ( u + w )

=

v∈Sy⊥

2−(n−r) , 0,

u + w ∈ Sy , u+w ∈ / Sy .

This proves (10). For u ∈ Wy , u + Sy = Wy , and hence Q′y Θy = 2−(n−r)

∑ |w⟩⟨u| = |Wy ⟩⟨Wy | .

u,w∈Wy

Remark 4.9. Thus, there is an efficient public test that accepts the coset superposition state |Wy ⟩: measure {Θy , I − Θy } using the predicate 1[P −1 (y, u) ̸=⊥]. On acceptance, apply H ⊗k , measure { Qy , I − Qy } using D(y, ·), Accept if and only if both outcomes are 1. 21

We now state the correctness and security properties of Construction 4.7. Theorem 4.10 (Construction 4.7 Correctness, adapted from [ÇGS26, Theorem 11]). For fixed oracles and y ∈ {0, 1}r , let h i ϵy,b = Pr OSS.VerO (y, b, u) = 0 : u ← OSS.SignO (y, |Wy ⟩⟨Wy | , b) . Let e1 = (1, 0, . . . , 0) ∈ Z2k . Then ( ϵy,b =

2− λ , 1[(by )1 ̸= b],

e1T Ay ̸= 0n−r , e1T Ay = 0n−r .

(12)

In particular, Construction 4.7 satisfies correctness with probability at least 1 − e(λ) where e(λ) := 2−λ + 2−(n−r) . Theorem 4.11 (Construction 4.7 security, [SZ25, Theorem 30]). For every quantum algorithm A making at most q queries to the oracles of Construction 4.2, 

(b0 , u0 ) ̸= (b1 , u1 ) ∧ O ← OSS.GenOracles(1λ ) : Pr O O (y, b0 , u0 , b1 , u1 ) ← AO (1λ ) OSS.Ver (y, b0 , u0 ) = OSS.Ver (y, b1 , u1 ) = 1



λ3 k 3 ( q + 2)3 ≤O 2λ 

If q is polynomial in λ, we get strong OSS security as per Definition 4.1. Remark 4.12 (Signing Unitary). Fix the oracles O , a verification key y, and a bit b. The signing alO on registers REΣ, where R gorithm admits a polynomial-time unitary oracle implementation Uy,b holds the signing state, E contains all auxiliary registers and measurement records, and Σ holds the O is obtained from OSS.SignO ( y, ·, b ) signature. The basis state |⊥⟩Σ denotes failure. The circuit Uy,b by Fact 3.1. For density operator ρ R corresponding to the signing key and the candidate signature u ∈ {0, 1}k ∪ {⊥}, h i O O † Pr[OSS.SignO (y, ρ R , b) = u] = Tr ( IRE ⊗ |u⟩⟨u|Σ )Uy,b . (13) (ρ R ⊗ |0⟩⟨0| EΣ )Uy,b We now consider the extension of this one bit signing scheme to a long message signing scheme by signing bit by bit. We note, [HV25; HSVZ26] gave more efficient and direct ways to achieve that. But, in this paper, we stick to the bit by bit signing paradigm. Construction 4.13 (Signatures for long messages). Set the message length L = poly(λ). Define OSS = (OSS.GenOracles, OSS.GenQKeyO , OSS.SignO , OSS.VerO ) as follows. From Construction 4.7, we use the corresponding oracles for one bit scheme and compose them component wise. (i) OSS.GenOracles(1λ ): sample independent instances Oc ← OSS.GenOracles(1λ ), c ∈ [ L], of Construction 4.7, and an independent random function Dig : {0, 1}∗ −→ {0, 1} L . Return the joint oracle O = (O1 , . . . , O L , Dig).

22

(14)

 .

(ii) OSS.GenQKeyO (1λ ): independently generate

( ac , Rc ) ← OSS.GenQKeyOc (1λ ),

c ∈ [ L ],

and output ( a, R1 · · · R L ), where a = ( a1 , . . . , a L ). (iii) OSS.SignO ( a, R1 · · · R L , M ): compute Dig( M ) = (b1 , . . . , bL ), run σc ← OSS.SignOc ( ac , Rc , bc ),

c ∈ [ L ],

and output σ = (σ1 , . . . , σL ). (iv) OSS.VerO ( a, M, σ ): reject malformed inputs. Otherwise, compute Dig( M ) = (b1 , . . . , bL ) and output L

∏ OSS.VerO (ac , bc , σc ). c

c =1

Thus, for a fixed joint oracle O and message M with Dig( M ) = (b1 , . . . , bL ), we have the verification key a = ( a1 , . . . , a L ), O the signing unitary Ua,M =

L O

UaOc ,bc c ,

the signing state | A a ⟩ =

L O

|Wac ⟩ ,

c =1 L O

the joint projector Π a =

c =1

Π ac = | A a ⟩⟨ A a | ,

c =1 L

the signature σ = (σ1 , . . . , σL ),

the verification procedure OSS.VerO ( a, M, σ ) = ∏ OSS.VerOc ( ac , bc , σc ). c =1

(15) Combining the one-bit component guarantees as given in Theorems 4.10 and 4.11, we get Theorem 4.14 (Long-message correctness and strong security, adapted from [SZ25, Theorem 30] and [HSVZ26, Lemma 71]). Let p : N → N be a polynomial in λ and set the message space to be Mλ = {0, 1}≤ p(λ) .. Then, the scheme of Construction 4.13 satisfies correctness and strong oneshot security as in Definition 4.1 against every quantum adversary making polynomially many total oracle queries for message space Mλ . Finally, we state the delayed collapsing property enjoyed by Construction 4.7. Definition 4.15 (Delayed Collapsing Poperty of Construction 4.7, adapted from [BGMS25b], Theorem 6). Consider the oracle distribution of Construction 4.2. For a two-stage QPT adversary λ A = (A0 , A1 ) and β ∈ {0, 1}, define the experiment DCollapseA β (1 ) as follows. (i) Sample

O = (P , P −1 , D) ← OSS.GenOracles(1λ ).

(ii) Give the first stage access to all three oracles and run

(y, b, U, Z ) ← A0P ,P

−1 , D

(1λ ),

where y ∈ {0, 1}r and b ∈ {0, 1} are classical, U is a k-qubit register, and Z denotes arbitrary residual quantum side information. We require A to be valid, meaning that measuring U in the computational basis produces a string u satisfying OSS.VerO (y, b, u) = 1. 23

(iii) If β = 0, do nothing. Otherwise, measure the register U in the computational basis. Let the ( β) resulting state on the registers U, Z be denoted by ρUZ . ( β)

(iv) Give (y, b, U, Z ) in state ρUZ to A1 , which has access only to the public inversion oracles: −1

d ← A1P ,P (y, b, U, Z ). Output d. The delayed-collapsing advantage of A is A AdvDCollapse (λ) := Pr[DCollapse0A (1λ ) = 1] − Pr[DCollapse1A (1λ ) = 1] .

We say that the one-bit OSS scheme is delayed collapsing if, for every valid two-stage QPT adversary A = (A0 , A1 ), A AdvDCollapse (λ) ≤ negl(λ). Bartusek et al. [BGMS25b] prove Construction 4.7 satisfies delayed collapsing.

4.2

Quantum fire

We first start with the definition of Quantum fire in the classical oracle model as done in [ÇGS26]. Definition 4.16. Let µ ∈ N be the security parameter. Quantum inputs and outputs are specified by registers written in capital letters. The states corresponding to these registers may be mixed. A public-key quantum fire scheme consists of an oracle-generation procedure and four QPT algorithms Fire = (Fire.GenOracles, Fire.SetupO , Fire.SparkO , Fire.VerO , Fire.CloneO ). 1. O ← Fire.GenOracles(1µ ): an oracle-generation procedure that samples a collection O of classical oracles queryable in superposition. All algorithms and adversaries have query access to them. The sampled oracles remain fixed throughout each experiment. 2. ( pk, sk ) ← Fire.SetupO (1µ ): this algorithm is run by the issuing authority. It takes the security parameter and outputs a classical public verification key pk and a classical secret key sk. 3. (s, F ) ← Fire.SparkO (sk ): this algorithm is run by the issuing authority. It takes the secret key and outputs a classical serial number s and a quantum flame register F. Each invocation uses independent randomness. 4. b ← Fire.VerO ( pk, s, F ), b ∈ {0, 1}: this public algorithm verifies an alleged flame F under serial number s and public key pk. 5. ( F0 , F1 ) ← Fire.CloneO ( pk, s, F ): this public algorithm returns two flame registers F0 , F1 , associated with the serial number s. We require the following two correctness guarantees from the scheme. Verification correctness. We require   O←Fire.GenOracles(1µ ) O O µ Pr Fire.Ver ( pk, s, F ) = 1 : ( pk,sk)←Fire.Setup (1 ) ≥ 1 − negl(µ). (s,F )←Fire.SparkO (sk)

24

(16)

Cloning correctness. For every polynomially bounded q = q(µ), sample

O ← Fire.GenOracles(1µ ), ( pk, sk) ← Fire.SetupO (1µ ), (s, F0 ) ← Fire.SparkO (sk). For i = 1, . . . , q(µ), execute

( Fi−1 , Fi ) ← Fire.CloneO ( pk, s, Fi−1 ). The assignment to Fi−1 replaces the input register by the first returned flame register. After all cloning operations, check bi ← Fire.VerO ( pk, s, Fi ),

i = 0, . . . , q(µ).

We require 

q(µ)

Pr 

^



(bi = 1) ≥ 1 − negl(µ).

(17)

i =0

All probabilities include oracle generation randomness, algorithmic randomness and measurement outcomes. We also require the following untelegraphability property. Definition 4.17. Let AO = (A1O , A2O ) be a pair of quantum adversaries making polynomially many queries to O in total, across both parties and the entire experiment. Their initial joint state is separable across the two parties and independent of the sampled oracles and the challenger’s setup randomness. Shared classical randomness is permitted. Define the game µ TELEGRAPHFire A O (1 ) between a challenger and an adversary as follows. 1. The challenger samples O ← Fire.GenOracles(1µ ), ( pk, sk) ← Fire.SetupO (1µ ), and gives pk to both parties. 2. For polynomially many rounds, A1O may submit a spark query. For each adaptive query, the challenger independently samples (s, F ) ← Fire.SparkO (sk ) and gives (s, F ) to A1O . No flame register is supplied to A2O . 3. A2O sends a classical message M to A1O . 4. Using M and its private state, A1O sends a classical string L to A2O . 5. Using L and its retained state, A2O outputs a classical serial number s∗ and a quantum register F∗ . 6. The challenger verifies

b ← Fire.VerO ( pk, s∗ , F ∗ )

and outputs b. The serial number s∗ need not have appeared during the spark-query phase. 25

The scheme satisfies untelegraphability if, for every such adversary AO making polynomially many oracle queries,   µ Pr TELEGRAPHFire (18) AO (1 ) = 1 ≤ negl( µ ). All probabilities include oracle generation randomness, algorithmic randomness and measurement outcomes. Now, we describe the oracle structure and other tools required for the Quantum Fire construction given in [ÇGS26] followed by the original construction. Construction 4.18 (Oracle collections, adapted from [ÇGS26, Sections 6.2]). Underlying OSS oracles. Sample an independent instance of oracle tuples as in Construction 4.2 with security parameter µ, i.e., r = 16µ(µ − 1), n = r + 24µ, k = n. (19) Consider, the predicate below derived from these source oracles. For y ∈ {0, 1}r , b ∈ {0, 1}, and u ∈ {0, 1}k , set D0 (y, b, u) = 1[u ∈ Wy ] ∧ 1[u1 = b]. (20) Thus, D0 is the one-bit verification predicate of (9). A Common Oracle Interface: We combine the four oracles P , P −1 , D , D0 into a single classical oracle G . An input to G specifies the operation and its arguments. Accordingly, we define the query set
Q = {forward} × {0, 1}n
⊔ {inverse, dual} × {0, 1}r × {0, 1}k
⊔ {verify} × {0, 1}r × {0, 1} × {0, 1}k . To represent every query by a string of the same length, choose a polynomially bounded ℓ ≥ r + k + 3, put Z = {0, 1}ℓ , and fix an injective encoding enc : Q −→ Z .

(21)

The encoding prepends two type bits to the arguments and pads with zeros to length ℓ. The processes of encoding, decoding and checking if an encoding is valid are efficient. The oracle G evaluates the query operation as follows:

G(enc(forward, x )) = P ( x ), G(enc(inverse, y, u)) = P −1 (y, u), G(enc(dual, y, u)) = D(y, u), G(enc(verify, y, b, u)) = D0 (y, b, u).

(22)

Inputs outside enc(Q) return ⊥. Fact 4.19. Direct access to G is reserved for the authority; public access will be provided through the oracle O2 defined below. Flame preparation. Recall that Construction 4.6 prepares a uniform superposition of verification keys and their coset states. Let Fire.GenG

26

denote this circuit with Y left unmeasured and its queries to P , P −1 implemented by the corresponding queries to G . Its output on the register YU is

|K ⟩YU = 2−r/2

∑

y∈{0,1}r

|y⟩Y |Wy ⟩U ,

(23)

and its remaining workspace is returned to zero. This state is going to be the flame state of the Fire scheme. Public Oracles: A public query to G must be accompanied by a tag. To define these tags, independently sample random functions H0 , H1 : {0, 1}r+ℓ −→ {0, 1}µ ,

h : Z −→ {0, 1}µ .

For a query z ∈ Z , a tag consists of a verification key y and two proposed hash values: p = (y, τ0 , τ1 ) ∈ {0, 1}r × {0, 1}µ × {0, 1}µ . It is valid precisely when both hash values are correct. Explicitly, we write Fire.Check for this predicate: Fire.Check(z, p) = 1[τ0 = H0 (y∥z)] ∧ 1[τ1 = H1 (y∥z)]. (24) The predicate is zero on malformed queries or tags. It is used inside the public oracles and is not itself a public oracle. Together, we consider the following oracle collection: ( Hb (y∥z), D0 (y, b, u) = 1, Ob (y, u, z) = b ∈ {0, 1}, ⊥, otherwise, ( G(z), Fire.Check(z, p) = 1, O2 (z, p) = ⊥, otherwise, (25) ( h(z), Fire.Check(z, p) = 1, N (z, p) = ⊥, otherwise, V (z, η ) = 1[η = h(z)]. For each bit b, the oracle Ob supplies the hash value Hb (y∥z) upon receiving a valid one-bit OSS signature u on b under y. A valid tag then permits O2 to return G(z) and N to return h(z). The oracle V performs a check. Malformed inputs return ⊥, except that V returns zero. The public oracle collection is O = (D , O0 , O1 , O2 , N, V ). (26) The functions G , D0 , H0 , H1 , h are not directly queryable for public. Remark 4.20. We note that, the validity of a supplied tag can be checked using the public oracle O2 by submitting the encoding of a forward query: Fire.Check(enc(forward, x ), p) = 1[O2 (enc(forward, x ), p) ̸=⊥] . Indeed, P ( x ) never returns ⊥.

27

(27)

Remark 4.21. Now, to fully describe the Fire construction, we need to build the Tag generation machinery explicitly. Write F = YU for the flame register. The algorithms use a common procedure Fire.TagO to obtain the two hash responses needed for a tag in registers R0 and R1 . For sake of continuity, we defer the detailed implementation of Fire.TagO to Section A.1. Signing a classical query. Verification uses a classical request z ∈ Z and tests a response against V. For the verification procedure only, consider the routine Fire.HashO ( F, z). This obtains a response by forming a tag and submitting it to N: (i) Measure Y, obtaining y. Initialize Z to |z⟩ and all auxiliary registers to zero. (ii) Apply Fire.TagO and measure R0 , R1 , obtaining τ0 , τ1 . (iii) Return N (z, (y, τ0 , τ1 )). Malformed tags give output ⊥. We note, measuring the register Y, potentially destroys the alleged flame. But this is compatible with the definition Definition 4.16 where verification only returns a bit. Although, one party interested in maintaining the flame can keep a cloned copy of it. We now are ready to describe the full Quantum Fire scheme of [ÇGS26]. Throughout this paper, we shall call this scheme CGS fire and the fire state as CGS flame. Construction 4.22 (Quantum Fire, adapted from [ÇGS26, Section 2.2]). The authority has direct access to G for spark, while verification and cloning use only O . The procedures of FireCGS are as follows. 1. O ← Fire.GenOracles(1µ ): sample the oracles as in Construction 4.18 and return the public collection (26). Retain private access to G for the authority. 2. ( pk, sk ) ← Fire.SetupO (1µ ): Sample an instance label s ← {0, 1}µ , independently of the sampled oracles, and set pk = s. The authority’s private oracle G is going to serve the purpose of its secret key sk. The oracles remain fixed throughout the rest of the experiment. 3. (s, F ) ← Fire.SparkO (sk ): run Fire.GenG (recall Equation (23)) on fresh zero registers and return

(s, F ),

F = YU,

ρ F = |K ⟩⟨K | .

4. b ← Fire.VerO ( pk, s, F ): reject unless s = pk and F has the prescribed size. Otherwise sample z ← Z uniformly, compute η ← Fire.HashO ( F, z), and return b = V (z, η ). 5. ( F0 , F1 ) ← Fire.CloneO ( pk, s, F ): on malformed inputs, return two zero registers of the prescribed flame size. We write F = YU for the input flame. The intention is to prepare a new flame on fresh registers by following the circuit of Construction 4.6, leaving its verification-key register Y unmeasured. but note to that, one needs access to the oracle G which is not available publicly. Instead, we implement its forward and inverse oracle calls using the public procedure below. e GO = (Fire.TagO )† UO Fire.TagO . U 2

(28)

where UO2 is the unitary implementing the oracle O2 . The details are given in, Section A.2. After completing the preparation circuit, return the original flame register as F0 and the newly prepared flame register as F1 . Discard all remaining workspace. 28

Now, We state the correctness and security guarantees of CGS fire at security parameter µ. Theorem 4.23 (Correctness and untelegraphability, adapted from [ÇGS26, Theorems 16–17]). Consider Construction 4.22 with the oracles of Construction 4.18 at security parameter µ. The construction satisfies verification correctness and cloning correctness in Definition 4.16, and untelegraphability in Definition 4.17. The next two remarks record stronger correctness guarantees for the cloning and coherent tag circuits. Remark 4.24 (Strong Cloning Correctness, adapted from [ÇGS26, Section 9.4]). Sample O ← Fire.GenOracles(1µ ) and ( pk, sk ) ← Fire.SetupO (1µ ), and put s = pk. Let |K ⟩ be the honest CGS flame in (23) for these oracles. The strong cloning guarantee, in trace-distance form, gives h i ⊗2 E D (Fire.CloneO ( pk, s, |K ⟩⟨K |), |K ⟩⟨K | ) ≤ negl(µ). (29) The expectation is over oracle generation and setup. Remark 4.25 (Coherent tag correctness, adapted from [ÇGS26, Section 9.4]). For each oracle and setup sample in Remark 4.24, let Π be the diagonal projector on ( Z, Y, R0 , R1 ) onto the basis values satisfying Fire.Check(z, (y, τ0 , τ1 )) = 1. It acts as the identity on all other registers. For every finite-dimensional register E, extend Fire.TagO and Π by the identity on E. Then " # 2
E sup ( I − Π)Fire.TagO |K ⟩ ⊗ |ψ⟩ ZE ⊗ |0⟩ ≤ negl(µ). (30) ∥|ψ⟩ ZE ∥=1

Here Fire.TagO is the circuit in (95), and |0⟩ comprises its response and signing workspace registers. The expectation is over oracle generation and setup. Remark 4.26 (Verification effect). Fix the oracles, pk, and s = pk. There is an operator B such that 0 ⪯ B ⪯ I,

Pr[Fire.VerO ( pk, s, ρ F ) = 1] = Tr( Bρ F )

(31)

for every density operator ρ F on the prescribed flame register.

5

Quantum Fire with Classical Cloning Key

In this section we define and present a privately verifiable variant of quantum fire that only allows delegated cloners with a classical token to sign. Cloning is impossible without such a token. We begin by formally defining this variant, as our syntax slightly deviates from that of Definition 4.16. Definition 5.1 (Privately Verifiable Quantum Fire with Classical Cloning Key). Let µ ∈ N be the security parameter. A Privately Verifiable Quantum Fire with Classical Cloning Key Scheme consists of an oracle generation procedure and a tuple of three QPT algorithms PVQF = (PVQF.GenOracles, PVQF.Spark, PVQF.Clone, PVQF.Ver) which work as follows: 29

1. O , aux ← PVQF.GenOracles(1µ ) : an oracle-generation procedure that samples a collection O of classical oracles queryable in superposition. 2. s, F, sk clone , sk ver ← PVQF.SparkO,aux (1µ ) : On input 1µ , this algorithm outputs a flame state F and serial number s, as well as secret keys sk clone and sk ver for cloning and verifying respectively. 3. F0 , F1 ← PVQF.CloneO (sk clone , s, F ): On input a secret cloning key sk clone , serial number s, and flame state F, the cloning algorithm outputs 2 flame registers F0 , F1 . 4. b ← PVQF.VerO (s, F, sk ver ): On input a secret verification key sk ver , a serial number s, and an alleged flame state F, outputs 0 or 1. Verification correctness, cloning correctness, and untelegraphability are analogous to Definition 4.16. Construction 5.2 (Privately Verifiable Quantum Fire with Classical Cloning Key). We now proceed to give a construction for this variant, which is essentially a slight modification of the quantum fire scheme given in [CNS26]. Similar to their scheme, this construction only allows for O(log(µ)) many clones, where µ denotes the security parameter. Here, all OSS operations refer to the long message variant described in Construction 4.13. 1. PVQF.GenOracles(1µ ): • Sample P, P−1 , D by running the oracle generator given in Construction 4.2 on input 1µ . • Set O = P, P−1 and aux = D. Output O , aux. 2. PVQF.SparkO,aux (1µ ): • Parse O as P, P−1 and run the key generation procedure • Set the OSS public key as pk and the OSS signing key as |sk ⟩ • Set s = pk, F = |sk ⟩, D = sk clone = sk ver . Output s, F, sk clone , sk ver . 3. PVQF.CloneO (sk clone , s, F ): • Parse sk clone as the oracle D and parse F as

(history, pkcur , |skcur ⟩). • Run

( pk0 , |sk0 ⟩), ( pk1 , |sk1 ⟩) ← OSS.KeyGen⊗2 (1λ ).

and compute σ ← OSS.SignD (|skcur ⟩ , pk0 ∥ pk1 ) . • Set F0 := (history∥( pk0 , pk1 , σ ), pk0 , |sk0 ⟩) and F1 := (history∥( pk0 , pk1 , σ ), pk1 , |sk1 ⟩) . • Output F0 , F1 . 4. PQVF.VerifyO (s, F, sk ver ): 30

• Parse s := pkroot , O := P, P−1 and F := (history, pkcur , |skcur ⟩) , where

  (1) (1) (T ) (T ) history = pk0 , pk1 , σ1 , . . . , pk0 , pk1 , σT .

• Define

(0)

(0)

pk0 = pk1 := pkroot . For every t ∈ {1, . . . , T }, compute     (t) (t) (t) (t) at := OSS.Verify pk(t−1) pk0 ∥ pk1 , σt ∨ OSS.Verify pk(t−1) pk0 ∥ pk1 , σt . 0

1

• If T = 0, reject unless pkcur = pkroot . If T ≥ 1, reject unless (T )

pkcur = pk0

or

(T )

pkcur = pk1 .

• Run the coset verification procedure outlined in Lemma 4.8 for all single bit OSS public key/secret key pairs in ( pk cur , |sk cur ⟩). Set a := 1 if all these tests pass, otherwise set a := 0. • Output a∧

T ^

! at

.

t =1

Correctness follows from OSS correctness. Theorem 5.3 (Security). Construction Construction 5.2 is a c log(µ)-clonable untelegraphable quantum fire scheme that is uncloneable for non-delegated cloners. Proof. Untelegraphability follows from the same reasoning given for Construction 1a in [CNS26]. Therefore, we now focus on proving unclonability for non-delegated cloners (i.e. ones without access to sk clone ). Assume there exists a QPT adversary A with nonnegligible winning probability. Let |sk ⟩ be one of the OSS signing keys that is used to sign the public key pair pk0 || pk1 when cloning. Recall that since we need to sign multiple bits, the signing key is multiple OSS signing keys which work for singular bits. Assume |sk ⟩ = |sk1 ⟩ . . . |sk L ⟩ comprises of L single bit OSS signing keys. We define 2L + 1 hybrid games H0 , . . . , H2L , where hybrid Hj is the modified adversarial cloning game defined above, except |sk j ⟩ is measured in the computational basis. We need 2L + 1 hybrids because we have L OSS signing keys for a single public key, and we provide signing keys for 2 public keys for cloning. By the delayed collapsing property of OSS, we know that each consecutive pair of hybrids are computationally indistinguishable from each other. Consider the final hybrid H2L , the Here both terminal string-signing keys have been measured: each terminal key consists of L independent single-bit OSS keys, so the hybrid measures 2L singlebit signing-key registers in total. 31

We construct an adversary B P,P reduction proceeds as follows:

−1 ,D

against the unforgeability of the single-bit OSS scheme. The

1. Using D, B generates an honestly distributed depth-t flame state f , for some t < c(λ). Let

( pk′0 , |sk′0 ⟩),

( pk′1 , |sk′1 ⟩)

be its two terminal OSS key pairs. Each pk′q , for q ∈ {0, 1}, is a tuple of single bit OSS public keys pk′q = (yq,1 , . . . , yq,L ), and its corresponding signing key is a tuple of OSS signing keys

|sk′q ⟩ =

L O

|τq,j ⟩ .

j =1

2. For each possible choice q ∈ {0, 1} of the parent signing key, B independently generates two fresh child key pairs: −1

( pk q,0 , |sk q,0 ⟩), ( pk q,1 , |sk q,1 ⟩) ← OSS.KeyGenP,P (1λ ). Thus, B generates four child key pairs in total. It retains all four child signing keys and defines Mq := pk q,0 ∥ pk q,1 . We write Mq = ( Mq,1 , . . . , Mq,L ). 3. For every q ∈ {0, 1} and j ∈ {1, . . . , L}, B uses D to compute uq,j ← SignP,P

−1 ,D

(|τq,j ⟩ , Mq,j ).

Let σq = (uq,1 , . . . , uq,L ). The reduction replaces the two terminal quantum signing-key registers |sk′0 ⟩ , |sk′1 ⟩ by the computational-basis states |σ0 ⟩ , |σ1 ⟩ , −1

respectively, and gives the resulting flame state to A P,P . 4. The messages M0 and M1 are independently and uniformly distributed because they are concatenations of independently generated OSS public keys. Furthermore, conditioned on (uq,j )1 = Mq,j , the value uq,j is uniformly distributed over the corresponding subset of the coset Syq,j . Consequently, (σ0 , σ1 ) has the same distribution as the outcomes obtained by measuring |sk′0 ⟩ and |sk′1 ⟩ in the computational basis. Therefore, the state given to A is distributed exactly as in H2L . 32

5. The adversary returns an alleged clone. First suppose that the public keys returned by the adversary in both clones are the same (i.e. pk0 = pk1 = y). Then if both clones passes verification, we know the coset verification procedure accepts when run on the registers storing the OSS signing key and public key (for both clones). This can only happen if the OSS signing key registers in both clones store precisely the coset state |Wy ⟩. If this is the case B can simply use the two |Sy ⟩ copies to sign 0 and 1, thus violating OSS security. 6. Next, suppose the public keys in the clones are different. Consider an alternative coset verification method to Lemma 4.8 that can be done without the D oracle. On classical input y and quantum input ρ, we define the algorithm CosetTest to do the following: (a) Measure ρ in the computational basis to get a string u (b) Output Accept if P−1 (y, u) = 1. Otherwise output Reject Let Wy be the coset corresponding to the hash value y and |Wy ⟩ be the OSS signing key corresponding to y. Then note that the probability CosetTest accepts on an arbitrary pair (y, ρ) is greater than or equal to the probability the coset verification algorithm from Lemma 4.8 accepts. Consider replacing this algorithm with CosetTest in the verification procedure of the scheme and keeping everything else as is. Then we know that any QPT adversary has a higher probability of winning the adversarial cloning game in this case compared to the original case. Therefore it suffices to prove any QPT adversary has a negligible winning probability after making this modification. Now since the public keys are different in this case, we know the adversary must have added some (q, c pk0 , c pk1 , b σ ), to one of the clones, where b := c M pk0 ∥ c pk1 b under the parent public key pk′q . Write and b σ verifies as a signature of M b σ = (ub1 , . . . , ubL ). There are two cases. b ̸ = Mq . • Case 1: M Choose an index j such that b j ̸= Mq,j . M By construction, OSS.Verify(yq,j , Mq,j , uq,j ) = 1. Since the adversary’s edge signature verifies, we must have b j , ubj ) = 1. OSS.Verify(yq,j , M Thus, B outputs
b j , ubj . yq,j , Mq,j , uq,j , M b j , these are valid signatures of two different bits under the same singleSince Mq,j ̸= M bit OSS public key. This violates OSS security. 33

b = Mq . • Case 2: M In this case,

(c pk0 , c pk1 ) = ( pk q,0 , pk q,1 ). ba be an alleged terminal signing key contained in the accepted child flame and Let T associated with pk q,a , for some a ∈ {0, 1}. Because the child passes the CosetTest version of verification, measuring an appropriate ba,ℓ (for some ℓ ∈ 1, . . . L) of T ba produces a string w satisfying single qubit component T P−1 ( pk q,a,ℓ , w) ̸=⊥ . Define b : = w1 . Then w is a valid OSS signature of b under pk q,a,ℓ : OSS.Verify( pk q,a,ℓ , b, w) = 1. Recall that B retained the corresponding honest child signing token |sk q,a,ℓ ⟩. It uses D to compute −1 w′ ← SignP,P ,D (|sk q,a,ℓ ⟩ , 1 − b). Therefore, The reduction outputs

OSS.Verify( pk q,a,ℓ , 1 − b, w′ ) = 1.
pk q,a,ℓ , b, w, 1 − b, w′ ,

which again consists of valid signatures of two different messages under the same single-bit OSS public key. Therefore, whenever A produces an accepted new child flame in H2L , B violates single-bit OSS unforgeability. Hence, Pr[H2L : CosetTest] ≤ negl(λ). By the delayed-collapsing hybrid argument, Pr[H0 : CosetTest] ≤ negl(λ). Finally, since acceptance by the algorithm in Lemma 4.8 implies acceptance CosetTest, the winning probability in the original unclonability game is also negligible.

6

Definition: Torch-Fire

In this section we give the formal definition of the torch-fire object in a classical oracle model. Definition 6.1. Let λ ∈ N be the security parameter. Quantum inputs and outputs are specified by registers written in Capital letters. The states corresponding to these registers may be in mixed states. A torch-fire scheme consists of an oracle-generation procedure and four QPT algorithms TF = (TF.GenOracles, TF.SetupO , TF.SparkO , TF.VerO , TF.CloneO ).

34

1. O ← TF.GenOracles(1λ ): an oracle-generation procedure that samples a collection O of classical oracles query-able in superposition. All algorithms and adversaries have query access to them. The sampled oracle remain fixed throughout each experiment.
2. pk, sk, (t1 , T1 ), . . . , (t R , TR ) ← TF.SetupO (1λ , 1R ): This algorithm is run by the issuing authority. It takes in the security parameter and a polynomially bounded R = R(λ) and outputs the public verification key pk, secret key sk and the torch states {(ti , Ti )}i∈[ R] . The values pk, sk, t1 , . . . , t R are classical, and T1 , . . . , TR are quantum torch registers. 3. (s, F ) ← TF.SparkO (sk ): This algorithm is run by the issuing authority. It takes in the secret key and outputs a classical serial number s and a quantum flame register F. Each invocation uses independent randomness. 4. b ← TF.VerO ( pk, s, F ), b ∈ {0, 1}: This public algorithm verifies an alleged flame F under serial number s and public key pk. 5. ( T ′ , F0 , F1 ) ← TF.CloneO ( pk, t, s, T, F ): This public algorithm returns a torch register T ′ , associated with the torch identifier t, and two flame registers F0 , F1 , associated with the serial number s. We require the following two correctness guarantees from the scheme. Verification correctness. For every polynomially bounded R. We require 

O

Pr TF.Ver ( pk, s, F ) = 1 :

O←TF.GenOracles (1λ )



pk,sk,(tℓ ,Tℓ )ℓ∈[ R] ←TF.SetupO (1λ ,1R )

≥ 1 − negl(λ).

(32)

(s,F )←TF.SparkO (sk)

Cloning correctness. For every polynomially bounded R, q sample

O ← TF.GenOracles(1λ )
pk, sk, (tℓ , Tℓ )ℓ∈[ R] ← TF.SetupO (1λ , 1R ) (s, F0 ) ← TF.SparkO (sk) Now for any j ∈ [ R], set T (0) = Tj . For i = 1, . . . , q(λ), execute

T (i) , Fi−1 , Fi ← TF.CloneO pk, t j , s, T (i−1) , Fi−1 . Note, the assignment to Fi−1 replaces the input register by the first returned flame register. After all cloning operations, check bi ← TF.VerO ( pk, s, Fi ),

i = 0, . . . , q(λ).

We require for every j ∈ [ R], 

q(λ)

Pr 

^



(bi = 1) ≥ 1 − negl(λ).

(33)

i =0

All probabilities include oracle generation randomness, algorithmic randomness and measurement outcomes. 35

Definition 6.2 (Global non-proliferation). Let R, m, N be polynomially bounded functions of λ, with 0 ≤ m ≤ R, and let the adversary AO = (A0O , A1O , . . . , AO N ) be a tuple of quantum polynomialtime algorithms. Define the game λ R SPLITTF AO (1 , 1 , m, N )

between a challenger and an adversary as follows.
1. The challenger samples O ← TF.GenOracles and pk, sk, (t j , Tj ) j∈[ R] ← TF.SetupO (1λ , 1R ) and gives pk to A0O . 2. The challenger answers polynomially many spark queries from A0O . For each adaptive query, it independently samples (s, F ) ← TF.SparkO (sk ) and gives (s, F ) to A0O . At any one point during this phase, A0O submits a set J ⊆ [ R] with | J | = m and receives ( Tj ) j∈ J from the challenger. No other torch registers are supplied. 3. The algorithm A0O outputs registers B1 , . . . , BN and terminates. Register Bi is assigned to AiO . Their joint state may be arbitrarily entangled. From this point onward, any classical or quantum pairwise communication between the parties (A1O , A2O , . . . , AO N ) is forbidden. No further torch or flame issuance is permitted, except for the challenge inputs specified in Step 4. 4. After the split, the challenger independently samples (si , Fi ) ← TF.SparkO (sk ), i ∈ [ N ]. It gives ( pk, s1 , . . . , s N ) to every party and gives Fi only to AiO . 5. The party i, i ∈ [ N ] executes ′ ′ , Fi,1 ) ← AiO ( pk, s1 , . . . , s N , Bi , Fi ). ( Fi,0 ′ , F ′ ) back to the challenger. and sends ( Fi,0 i,1

6. The challenger checks ′ bi,a ← TF.VerO ( pk, si , Fi,a ),

i ∈ [ N ], a ∈ {0, 1},

and sets Xi = bi,0 bi,1 . The game outputs 1 if N

∑ Xi ≥ m + 1,

i =1

and outputs 0 otherwise. The scheme satisfies the global non-proliferation property if, for every R, m, N and every adversary AO as above,   λ R Pr SPLITTF ( 1 , 1 , m, N ) = 1 ≤ negl(λ). (34) O A All probabilities include oracle generation randomness, algorithmic randomness and measurement outcomes. Remark 6.3. We note that for m = 0, this property implies that an adversary without given a torch, cannot clone a flame state, except with negligible probability. 36

Definition 6.4 (Untelegraphability). Let AO = (A1O , A2O ) be a pair of quantum adversaries making polynomially many queries to O in total, across both parties and the entire experiment. The initial joint state of (A1O , A2O ) is separable across the two parties (i.e., they strictly do not have any shared entanglement) and independent of the challenger’s setup randomness. Shared classical randomness is permitted. Define the game λ R TELEGRAPHTF A O (1 , 1 ) between a challenger and an adversary as follows.
1. The challenger samples O ← TF.GenOracles and pk, sk, (t j , Tj ) j∈[ R] ← TF.SetupO (1λ , 1R ) and gives pk to both parties. 2. The adversary specifies disjoint sets J1 , J2 ⊆ [ R]. The challenger gives ( Tj ) j∈ J1 to A1O and ( Tj ) j∈ J2 to A2O . 3. For polynomially many rounds, A1O may submit a spark query. For each adaptive query, the challenger independently samples (s, F ) ← TF.SparkO (sk ) and gives (s, F ) to A1O . No flame register is supplied to A2O . 4. A2O sends a classical message M to A1O . 5. Using M and its private state, A1O sends a classical string L to A2O . 6. Using L and its retained state, A2O outputs a classical serial number s∗ and a quantum register F∗ . 7. The challenger verifies

b ← TF.VerO ( pk, s∗ , F ∗ )

and outputs b. The serial number s∗ need not have appeared during the spark query phase. The scheme satisfies untelegraphability if, for every polynomially bounded R and every such adversary AO ,   λ R Pr TELEGRAPHTF (35) AO (1 , 1 ) = 1 ≤ negl( λ ). All probabilities include oracle generation randomness, algorithmic randomness and measurement outcomes.

7

Construction of Torch-fire

7.1

Construction

The construction uses the long-message OSS signing states in (15) and the CGS flame state in (23). A torch is one such OSS signing state. A flame has two parts: an independently generated OSS signing state, called its anchor, and a CGS flame state. The two parts are cloned separately. For the CGS flame part, we use the public cloning procedure of CGS fire. For the anchor, we use a procedure whose oracle queries require signatures from the torch and anchor, together with a CGS tag. We first describe formally the component wise machinery and these oracle interfaces, then give a construction of torch-fire.

37

Parameters. Let λ ≥ 2 be the security parameter of the overall torch-fire scheme. For the long-message OSS of Construction 4.13, we use the parameters L = λ,

r = 16λ(λ − 1),

n = r + 24λ,

k = n.

For the CGS fire of Constructions 4.18 and 4.22, we use the parameters below. We distinguish its dimensions by writing a subscript K throughout. µ = λ2 ,

rK = 16µ(µ − 1),

nK = rK + 24µ,

k K = nK

Oracle collections for each instance. Fix a polynomially bounded integer R ≥ 0, the number of torches. We use the per-instance oracle convention of [ÇGS26, Section 8]: each instance has its own sampled oracle collection, with public and private access specified below. We can lift it to the standard oracle model where there is one global oracle and the Setup procedure samples public key, secret key to specify the corresponding oracles instead of outputting oracle tuples. Oracle sampling and evaluation need not be efficient; the procedures using these oracles are QPT with their prescribed access. The public key is pk = R; the associated oracle collection specifies the instance and is implicit throughout. For each instance, the construction uses one common OSS oracle collection for its torches, a family of OSS oracle collections for its anchors, and one CGS fire oracle collection. Fix one such instance and sample the following collections. (i) O T ← OSS.GenOracles(1λ ): sample one long-message OSS oracle collection as in Construction 4.13. All R torches use this same collection. (ii) For every ℓ ∈ {0, 1}λ , sample

O A,ℓ ← OSS.GenOracles(1λ ). as in Construction 4.13. Each ℓ selects an independent long-message OSS oracle collection for anchors. (iii) OK ← Fire.GenOracles(1µ ): sample the CGS public oracle collection in (26). Its underlying generation oracle is denoted by G , as in (22). Direct access to G is private to the issuing authority and is not included in OK . Every long-message OSS oracle collection contains L one-bit components and its own digest oracle (Equation (14)). Torch verification keys.

For the fixed instance, sample independently t j = (t j,1 , . . . , t j,L ) ← ({0, 1}r ) L ,

j ∈ [ R ].

These are long-message OSS verification keys relative to O T . Uniform sampling agrees with the key distribution in Constructions 4.6 and 4.13. Publish the keys through the oracle ( t j , j ∈ [ R ], T ( j) = Tpub = {t j : j ∈ [ R]}. (36) ⊥, otherwise,

38

Private generation data for the issuing authority. For each published torch key t j and component c ∈ [ L], the issuing authority receives the matrix and shift defining Wt j,c (Recall Equation (5)) in component c of O T . Write these private classical data as
tdT = At j,c , bt j,c j∈[ R], c∈[ L] . Their total size is polynomial in λ for polynomially bounded R. Knowing At j,c and bt j,c , by the relation (7), the authority can prepare the torch registers

| Tj ⟩ =

L O

|Wt j,c ⟩

(37)

c =1

Separately, the authority retains private access to G to prepare the CGS flame part during spark. Neither tdT nor direct access to G is public. Anchor labels and flame serials. An anchor has a source label ℓ and a verification key a relative to O A,ℓ . The pair is the flame serial: s = (ℓ, a),

a = ( a1 , . . . , a L ) ∈ ({0, 1}r ) L .

ℓ ∈ {0, 1}λ ,

(38)

The signing registers. For a torch verification key t ∈ Tpub and a flame serial s = (ℓ, a), write the corresponding signing states from (15) as

| Tt ⟩T =

L O

|Wtc ⟩Tc ,

T = T1 · · · TL ,

c =1

| Aa ⟩ A =

L O

(39)

|Wac ⟩ Ac , A = A1 · · · A L .

c =1

In the first line, Wtc belongs to component c of O T . In the second, Wac belongs to component c of O A,ℓ . The CGS flame part and the flame. Let |K ⟩ be the state in (23) relative to OK . The honest flame with serial s is the state of the register F = AK. Hence, the flame is:

| Fs ⟩ F = | A a ⟩ A ⊗ |K ⟩K .

(40)

Remark 7.1. Having described the structure of the flame and the torch, we now move towards building a torch-fire scheme as in Definition 6.1. To build that, along with the oracles O T , {O A,ℓ }ℓ , OK , we need some more fine-grained access structure which we build next. Affine functions for a fixed verification key. Cloning a flame with serial s = (ℓ, a) needs to prepare an additional register in |Wac ⟩ for each c ∈ [ L]. This task, ultimately requires preparing |Wy ⟩ for a specified key y in the corresponding one-bit OSS source. We define the affine functions used in this preparation. Consider one anchor component and a key y ∈ {0, 1}r . Using its matrix Ay , shift by , and coset Wy from Construction 4.2, define affiney,0 (w) = Ay w + by , ( w, u = Ay w + by for some w ∈ {0, 1}n−r , affiney,1 (u) = ⊥, u ∈ / Wy , 39

w ∈ {0, 1}n−r , u ∈ {0, 1}k .

(41)

Full column rank makes the inverse coordinate w unique. Remark 7.2. The crucial thing is, these affine functions do not have public access; access to them is specified below. Critically, if one has access to these affine functions corresponding to a y ∈ {0, 1}r , that party can prepare the corresponding coset state as follows. Note, the contrast between this coset preparation procedure against that one in Construction 4.6 lies in which oracles they are allowed to access. The coset-state preparation circuit. n − r, k qubits to zero and apply H

Given the two affine queries for y, initialize registers X, Y of ⊗(n−r )

X |0n−r ⟩ X |0k ⟩Y −−−− → 2−(n−r)/2 ∑ |w⟩ X |0k ⟩Y

w

affiney,0 : X →Y

−−−−−−−→ 2−(n−r)/2 ∑ |w⟩X | Ay w + by ⟩Y

(42)

w

affiney,1 : Y → X

−−−−−−−→ |0n−r ⟩ X |Wy ⟩Y . Messages for anchor cloning We want to build a structure such that a party holding a torch can clone an anchor but a party without a torch cannot. To do so, we want, to clone the anchor part of a flame using the torch, signatures (of some underlying messages) are needed from both the anchor and the torch treating them as long-message OSS signing states. We set the underlying messages to be signed in the following way. For s = (ℓ, a) and a torch verification key t, set the messages M A (s, t) = 0∥⟨s, t⟩, MT (s, t) = 1∥⟨s, t⟩, (43) where

⟨s, t⟩ = ℓ∥ a1 ∥ · · · ∥ a L ∥t1 ∥ · · · ∥t L . The anchor signs M A (s, t), and the torch signs MT (s, t), using Construction 4.13. These messages have length 1 + λ + 2Lr and remain fixed throughout one cloning call. Also note, the messages are hashed to L bit digests by the corresponding digest oracles (Equation (14)) in O A,ℓ and O T . Anchor-affine queries. For an anchor, to request an affine value (Equation (41)), we need to specify q = (s, t, c, e, u), c ∈ [ L ], e ∈ {0, 1}, s = (ℓ, a) The query asks for affineac ,e (u) in component c of O A,ℓ . Its input length is n − r for e = 0 and k for e = 1. Let Qaffine be the set of these well-formed queries, with s as in (38) and t ∈ ({0, 1}r ) L . The key t specifies the torch under which the accompanying torch signature is verified. Encoding the query for a CGS tag. We also want to enforce, a party who holds an existing torch-fire state should only be able to clone the anchor part. To enforce that, we observe a party holding an existing torch-fire state can generate a valid CGS tag using its CGS flame part as in Equation (95). Thus, in addition to the two OSS signatures, the gate keeping oracle Γ in Construction 7.3 checks a CGS tag before answering a complete affine query q = (s, t, c, e, u). Recall from (21) and (22) that a forward query to the CGS fire interface is specified by an nK -bit string. We encode q into such a string. 40

Let [c]λ denote the binary representation of c with leading zeros to make its length exactly λ. Since c ∈ [ L] and L = λ, this suffices to represent every component index. Define code : Qaffine −→ {0, 1}nK

(44)

by concatenating the fields of q in the following order and appending zeros until the total length is nK : code(q) = ⟨s, t⟩∥[c]λ ∥e∥u∥0 · · · 0. Here ⟨s, t⟩ is the concatenation already defined in (43). It has length λ + 2Lr, since |ℓ| = λ. The bit e determines the length of u: n − r for e = 0 and k for e = 1. Thus all field boundaries are known, and the encoding is injective and efficiently decodable. Our choice of CGS fire security parameter µ = λ2 provides enough space for this encoding. Indeed, nK = 16µ2 + 8µ = 16λ4 + 8λ2 , whereas the concatenated fields before padding have length at most 2λ + 2Lr + 1 + k ≤ 32λ3 ≤ nK

( λ ≥ 2).

Using the CGS fire encoding from (21), set xq = code(q),

zq = enc(forward, xq ) ∈ Z .

The encoding enc and query space Z belong to the CGS fire source OK of this instance. The circuit Fire.TagOK from (95) computes a tag p with query input zq , and Γ checks the supplied tag p using Fire.Check(zq , p). By (27), this check can also be performed through the public oracle O2 associated with the CGS fire oracle collection OK . Construction 7.3 (The Γ oracle). The public oracle Γ receives a query q = (s, t, c, e, u), two OSS signatures σA , σT , and a CGS tag p. Writing s = (ℓ, a), it checks q ∈ Qaffine

∧

t ∈ Tpub

∧

OSS.VerO A,ℓ ( a, M A (s, t), σA ) = 1

∧ ∧

OSS.VerOT (t, MT (s, t), σT ) = 1

(45)

Fire.Check(zq , p) = 1.

Its response is ( Γ(q, p, σA , σT ) =

affineac ,e (u), ⊥,

if (45) holds, otherwise.

(46)

All component oracles belong to the fixed instance. The returned affine query value belongs to component c of O A,ℓ . The tag predicate is (24) for OK . Malformed inputs return ⊥. For the fixed instance, the full public collection is   O = Opub = OT , (O A,ℓ )ℓ∈{0,1}λ , OK , T , Γ .

The full public oracle collection.

(47)

All algorithms and adversaries have quantum query access to O . Anchor queries specify ℓ; the additional interfaces use their inputs defined above. The issuing authority alone receives tdT and retains private access to G .

41

Coherent preparation of an affine query. Fix a serial s = (ℓ, a), a published torch key t ∈ Tpub , a component c ∈ [ L], and e ∈ {0, 1}. Let, the unitary RO c,e describes how the anchor A, torch T, and CGS flame part K are used to request a value of affineac ,e from Γ in a coherent way. We defer its implementation details to Section B.1. Now we are ready to describe the full torch-fire protocol. Construction 7.4 (Torch-fire). The procedures use the oracle collection in (47), with the instance implicit throughout. Setup also receives tdT , and spark uses private access to G . All Fire subroutines below use the CGS fire source OK . Its public key and serial are both taken to be 0µ in these calls. 1. O ← TF.GenOracles(1λ , 1R ).   Sample the oracles O T , (O A,ℓ )ℓ∈{0,1}λ , OK and torch verification keys T according to the distributions specified above. Define Γ from the same underlying samples. Return the full public collection (47). Provide the issuing authority with tdT and private access to G for this instance. These functions remain fixed throughout the experiment. 2.

pk, sk, (t j , Tj ) j∈[ R] ← TF.SetupO (1λ , 1R ). (i) Set the public and secret keys. Set pk = R. The authority’s private access to G serves as its secret key sk. (ii) Read the torch keys using T . Obtain t j = T ( j) for every j ∈ [ R]. Abort if two keys coincide.
(iii) Prepare the torches using tdT = At j,c , bt j,c j∈[ R], c∈[ L] . For every j ∈ [ R] and c ∈ [ L], run the coset-state preparation circuit (42) for y = t j,c . Denote the resulting signing register by Tj,c and put Tj = Tj,1 · · · Tj,L . Return pk, sk, (t j , Tj ) j∈[ R] . The state of each torch is ρ Tj = | Tt j ⟩⟨ Tt j | ,

| Tt j ⟩ =

L O

|Wt j,c ⟩ .

c =1

3. (s, F ) ← TF.SparkO (sk ). Prepare a fresh anchor and CGS flame part. (i) Generate the anchor using O A,ℓ . Sample ℓ ← {0, 1}λ and run

( a, A) ← OSS.GenQKeyO A,ℓ (1λ ). This invokes Construction 4.6 in each anchor component, using its public P , P −1 interfaces. It produces verification key a and signing state | A a ⟩⟨ A a |. (ii) Generate the CGS flame part using G . Prepare K by the circuit for (23), using the authority’s private access to G for its forward and inverse queries. This prepares |K ⟩⟨K | for the same instance. Return s = (ℓ, a),

F = AK,

ρ F = | A a ⟩⟨ A a | ⊗ |K ⟩⟨K | = | Fs ⟩⟨ Fs | .

Each invocation uses fresh randomness and fresh registers. 42

4. b ← TF.VerO ( pk, s, F ). Reject malformed classical inputs or incorrect register sizes. Parse s = (ℓ, a) and F = AK, and test the two components. (i) Test the anchor using O A,ℓ . Apply the test of Lemma 4.8 to every component of A. Each test uses P −1 for coset membership and D for dual-subspace membership. The joint accepting projector is Πa =

L O

Π ac = | A a ⟩⟨ A a | .

c =1

If any component rejects, return zero. (ii) Test the CGS flame part using OK . Return the output of b ← Fire.VerO (0µ , 0µ , K ). This procedure uses D , O0 , O1 to form a tag, N to obtain a response, and V to check that response. With B denoting the CGS flame verification effect from (31), the accepting effect on F is VsF = Π a ⊗ B.

(48)

5. ( T ′ , F0 , F1 ) ← TF.CloneO ( pk, t, s, T, F ). Reject malformed classical inputs or incorrect register sizes by returning zero registers of the prescribed output sizes. Otherwise parse s = (ℓ, a) and F = AK. (i) Check the torch key using T . Read the published keys and check t ∈ Tpub . If the check fails, return zero registers of the prescribed sizes. (ii) Clone the CGS flame part using OK . Run

(K0 , K1 ) ← Fire.CloneO (0µ , 0µ , K ). This uses D , O0 , O1 to prepare tags and O2 to implement the CGS generation queries. (iii) Prepare a second anchor through Γ. Use A, T, K0 as the resources for the affine-query. For each c ∈ [ L], initialize Xc , Yc to zero, of sizes n − r, k, respectively, and execute ⊗(n−r )

HXc

RO c,0 : Xc → Yc ,

,

RO c,1 : Yc → Xc .

This is essentially, the steps of the coset state the preparation procedure of (42). Each affine query uses O A,ℓ and O T for the two signatures, OK for the tag, and Γ for the affine value. Return

T ′ = T,

F0 = AK0 ,

F1 = Y1 · · · YL K1 ,

and discard the remaining workspace. The four algorithms TF.SetupO , TF.SparkO , TF.VerO , TF.CloneO are QPT with the oracle access and private data specified above, for polynomially bounded R. 43

7.2

Correctness

We prove verification and cloning correctness for the construction in Section 7.1. An honest flame consists of an anchor A and a CGS flame part K. Verification tests these two registers separately. Cloning first produces two CGS flame registers, then uses the original anchor, the torch, and one CGS flame register to prepare a second anchor through Γ. It, though, requires a proof that these affine queries also preserve the three resources used to make them. We establish this for one query, then for one cloning call, and finally for repeated cloning. Throughout, L = λ, n − r = 24λ, µ = λ2 , and D (ρ, σ) = 12 ∥ρ − σ∥1 . Expectations are over the sampling of the oracles and classical keys. In principle, we want to argue all the steps relevant to the torch-fire construction in Section 7.1 succeeds together, as desired, except with negligible probability. Lemma 7.5. Fix the oracles, published torch keys, and an honest spark serial s = (ℓ, a). We have,   R −rL O ∆setup := Pr[TF.Setup aborts] ≤ 2 = negl(λ). (49) 2 Proof. Setup aborts precisely when two independently sampled torch keys coincide, so   R −rL ∆setup ≤ ∑ Pr[t j = t j′ ] = 2 . 2 1≤ j < j ′ ≤ R

Signing errors. Affine access requires the two OSS signatures and the CGS tag in (45) to pass their checks. For the OSS checks, let ϵy,b be the pointwise error in Theorem 4.10. Set e(λ) = 2−λ + 2−24λ = negl(λ) and L

1

e A = ∑ ∑ ϵac ,b ,

E[e A ] ≤ 2Le(λ),

c =1 b =0 R

L

(50)

1

eT = ∑ ∑ ∑ ϵt j,c ,b ,

E[eT ] ≤ 2RLe(λ).

j =1 c =1 b =0

If bcA ( M ) and bcT ( M ) denote the cth bits of the anchor and torch digests of M, then Construction 4.13 and Remark 4.12 gives L

Pr[anchor signature on M is rejected] ≤ ∑ ϵac ,bcA ( M) ≤ e A , c =1 L

Pr[torch j signature on M is rejected] ≤ ∑ ϵt j,c ,bcT ( M) ≤ eT . c =1

CGS errors. For the CGS component, we need verification, joint cloning, and tag correctness. With B from (31) and the tag projector PK from Remark 4.25, define ever = 1 − Tr( B |K ⟩⟨K |),   ecl = D Fire.CloneO (0µ , 0µ , |K ⟩⟨K |), |K ⟩⟨K |⊗2 , etag =

sup ∥|ψ⟩ ZE ∥=1

O

( I − PK )Fire.Tag (|K ⟩ ⊗ |ψ⟩ZE ⊗ |0⟩) 44

2

(51) .

By Theorem 4.23 and Remarks 4.24 and 4.25, E[ever + ecl + etag ] ≤ negl(λ),

µ = λ2 .

(52)

Affine query access. The anchor-preparation circuit (42) uses the same anchor, torch, and CGS flame across its affine queries. We therefore need the coherent implementation of (97) for the requested affine operation while preserving these three resources. In principle, we want to argue, since Γ agrees with the ideal affine oracle whenever its checks pass, the error probability is negligible. Lemma 7.6. Fix an honest serial s = (ℓ, a) and t ∈ Tpub , and set d = min{1, e A + eT + etag }.

(53)

For any normalized |ϕ⟩ XCE , let

|ψ⟩ = | A a ⟩ | Tt ⟩ |K ⟩ ⊗ |ϕ⟩XCE ⊗ |0⟩W , where X, C are the affine-input and answer registers, E, W are auxiliary workspace registers. Then, for every c ∈ [ L] and e ∈ {0, 1},

√
RO − U | ψ ⟩ ≤ 2 d, affine c,e ac ,e

(54)

where the ideal query acts only on X, C. Moreover, E[d] ≤ 2L( R + 1)e(λ) + E[etag ] ≤ negl(λ).

(55)

Proof. The proof is given at Section B.2. Theorem 7.7 (Verification and cloning correctness). Construction 7.4 satisfies (32) for every polynomially bounded R ≥ 0, and (33) for every polynomially bounded R, q and every j ∈ [ R]. Proof. Fix a successful setup and the honest states from Lemma 7.5. 1. Verification.

By (48) and Lemma 4.8, Tr[(Π a ⊗ B) | Fs ⟩⟨ Fs |] = Tr(Π a | A a ⟩⟨ A a |) Tr( B |K ⟩⟨K |) = 1 − ever .

Hence (49) and (52) give verification error at most ∆setup + E[ever ] = negl(λ). 2. One cloning call. Let ρ be the cloning output on | Tt ⟩⟨ Tt | ⊗ | Fs ⟩⟨ Fs |. Compare it with ρe, obtained by replacing the CGS cloning output with |K ⟩⟨K |⊗2 before preparing the second anchor. This replacement changes the state by trace distance ecl i.e. D (ρ, ρe) ≤ ecl . It remains to compare the 2L anchor-affine queries (2 calls per component) with the ideal queries in (42). With workspace retained, let |Ψh ⟩ be the final state when the first h queries are ideal and the rest actual, for 0 ≤ h ≤ 2L. Write RO h , Uh for the two versions of query h, and | ψh ⟩ for its input after the ideal prefix. That prefix preserves A, T, K0 , so Lemma 7.6 gives

√ ∥|Ψh−1 ⟩ − |Ψh ⟩∥ = (RO h − Uh ) | ψh ⟩ ≤ 2 d.

45

Summing over the queries, 2L √ ∥|Ψ0 ⟩ − |Ψ2L ⟩∥ ≤ ∑ ∥|Ψh−1 ⟩ − |Ψh ⟩∥ ≤ 4L d. h =1

The ideal circuit (42) has output

|Ψ2L ⟩ = | Tt ⟩ ⊗ | Fs ⟩⊗2 ⊗ |0⟩work . Passing to trace distance, tracing out workspace, and adding the CGS cloning error yields   √ D ρ T ′ F0 F1 , | Tt ⟩⟨ Tt | ⊗ | Fs ⟩⟨ Fs |⊗2 ≤ ecl + 4L d = negl(λ).

(56)

3. Repeated cloning. Fix j ∈ [ R] and t = t j . Let ρi be the joint state of the torch and all i + 1 flames after i calls in Definition 6.1, and set τi = | Tt ⟩⟨ Tt | ⊗ | Fs ⟩⟨ Fs |⊗(i+1) . The ith cloning operation Ci acts on T, Fi−1 and leaves F0 , . . . , Fi−2 untouched. Contractivity and (56) imply D (ρi , τi ) ≤ D (Ci (ρi−1 ), Ci (τi−1 )) + D (Ci (τi−1 ), τi ) √ ≤ D (ρi−1 , τi−1 ) + ecl + 4L d. Since ρ0 = τ0 , induction gives

4. Acceptance of all flames. bound give

√
D (ρi , τi ) ≤ i ecl + 4L d .

(57)

For the failure event E = {∃i ∈ {0, . . . , q} : bi = 0}, (57) and a union Pr[E ] ≤ Pr[E ] + D (ρq , τq ) ρq

τq

√
≤ (q + 1)ever + q ecl + 4L d .

√ p Averaging and using E[ d] ≤ E[d], we obtain

Pr[cloning correctness fails] ≤ ∆setup + q E[ecl ] + 4L

q

E[d] + (q + 1)E[ever ]

(58)

≤ negl(λ). The last inequality uses (49), (52), and (55), with R, q, L polynomially bounded.

7.3

Untelegraphability

We now prove the Construction 7.4 satisfies the untelegraphability property as in Definition 6.4. By (48), the accepting effect satisfies Π a ⊗ B ⪯ I A ⊗ B. We therefore reduce to CGS untelegraphability by discarding the output anchor.

46

Theorem 7.8. for every polynomially bounded R and every polynomial query bounded pair of adversaries AO = (A1O , A2O ), h i λ R Pr TELEGRAPHTF ( 1 , 1 ) = 1 ≤ negl(λ). (59) O A Proof. Suppose A is an adversary to the untelegraphability game of the torch-fire object (Definition 6.4) making at most Q public-oracle queries and v spark requests. Using that, we construct an adversary (B1OK , B2OK ) for the untelegraphability game of the CGS fire scheme as per Definition 4.17 at µ = λ2 , with Bi running Ai . 1. Simulating the oracles. Use the challenged CGS collection as OK in (47); write b s for its public key and serial. Sample the remaining torch and anchor data, including digest oracles and published keys, as in Section 7.1, using shared classical randomness independent of OK . Both simulated adversaries (B1OK , B2OK ) can then evaluate O T , (O A,ℓ )ℓ , and T locally, forward OK queries to the challenger, and simulate setup with pk = R. 2. Simulating Γ. For a well-formed query q = (s, t, c, e, u), let χ(q, σA , σT ) be the predicate which is 1 if the torch membership check and two OSS checks in (45) pass. Both χ and affineac ,e (u) are determined by the sampled oracles and data. For the tag check, put zq = enc(forward, code(q)). Since G(zq ) = P (code(q)) ̸=⊥, (27) gives Fire.Check(zq , p) = 1[O2 (zq , p) ̸=⊥].

(60)

Consequently, (46) becomes ( Γ(q, p, σA , σT ) =

χ(q, σA , σT ) = 1 ∧ O2 (zq , p) ̸=⊥, otherwise.

affineac ,e (u), ⊥,

3. Simulating issuance and output. (i) Torches. For the chosen disjoint sets J1 , J2 , each Bi prepares its assigned torches from the sampled matrices and shifts. By Lemma 7.5, this gives the required joint state ρ TJ1 TJ2 =

O

| Tt j ⟩⟨ Tt j | .

j∈ J1 ∪ J2

(ii) Spark. For each request, B1 obtains a fresh K from the CGS challenger, samples ℓ ← {0, 1}λ , and runs OSS.GenQKeyO A,ℓ (1λ ) to obtain ( a, A). It returns ρ F|s = | A a ⟩⟨ A a | ⊗ |K ⟩⟨K | ,

(s, F ) = ((ℓ, a), AK ), exactly as in Construction 7.4.

(iii) Output. Given s∗ = (ℓ, a) and F ∗ = AK, party B2 returns

(s∗ , ρ AK ) 7−→ (b s, Tr A ρ AK ). The classical messages exchanged between (A1O , A2O ) are kept unchanged. 47

4. Comparing success probabilities. Let pTF , pCGS be the respective success probabilities, and let ρsAK be the (possibly subnormalized) state on valid outputs with serial s. The CGS effect B is the same for every s. Thus, Theorem 4.23 gives h i pTF = ∑ Pr s∗ = s ∧ TF.VerO accepts s=(ℓ,a)

"

=E

∑

# Tr[(Π a ⊗ B)ρsAK ]

s=(ℓ,a)

"

≤E

∑ Tr[( IA ⊗ B)ρsAK ]

#

(61)

s=(ℓ,a)

"

=E

∑ Tr[ B Tr A (ρsAK )]

#

s=(ℓ,a)

≤ pCGS ≤ negl(µ) = negl(λ). The first inequality uses Π a ⪯ I A and B ⪰ 0.

8

Extraction and Global Non-proliferation

We prove the global non-proliferation property (Definition 6.2) for Construction 7.4 in the perinstance oracle model of Section 7.1. All public oracles are as shown in (47). The idea is to convert successful cloning at several separated locations i ∈ [ N ] into extracting valid torch signatures for their respective challenge labels ℓi . The experiment.

Fix polynomially bounded R, m, N, with 0 ≤ m ≤ R, and an adversary

AO = (A0O , A1O , . . . , AO N) as in Definition 6.2. Let v is an upper bound on the number of pre-split spark queries, and let Qpre is upper bound on the number of pre-split oracle queries. The challenge serial at location i is: si = (ℓi , ai ),

ai = ( ai,1 , . . . , ai,L ) ∈ ({0, 1}r ) L .

ℓi ∈ {0, 1}λ ,

Let Xi indicate that both output flames (outcome of the cloning experiment) at location i verify under the serial si . The winning event is ∑i Xi ≥ m + 1. It is trivially impossible when m ≥ N, so throughout the proof we may assume m < N and hence N ≥ 1. Distinct labels ℓ ∈ {0, 1}λ . Define the ideal experiment by additionally declaring failure if any two labels ℓ among the v pre-split and N challenge spark queries coincide. If preal and pideal are the real and ideal winning probabilities for an adversary, respectively, then a union bound gives   v + N −λ preal ≤ pideal + 2 = pideal + negl(λ) (62) 2 for polynomial v(λ), N (λ).

48

8.1

Extraction from separated computations

We prove a general extraction lemma for N local oracle computations on a possibly entangled input. Its application in the context of torch-fire game is given in Section 8.2. Previous work considers simultaneous extraction from two entangled oracle algorithms [CMP24], or from a common quantum input with essentially fixed outputs [CLPY25]. Our lemma compares, for every d, the probability that at least d non-communicating parties accept with the probability that at least d local extractors output witnesses. The extractors use only the modified oracles. The input spaces. For each location i ∈ [ N ], let Hi be its input space and Wi its workspace. Let N ρ be a possibly subnormalized joint density operator on H = iN=1 Hi , and let ρi be its reduced state at location i: ρ ⪰ 0, Tr ρ ≤ 1, ρi = TrNk̸=i Hk (ρ). Each computation operates only on its own input and workspace; the locations do not communicate. The two oracle computations. of computation given by:

At location i, consider the q-query, original and modified mode 1 1 Ui1 = Gi,q Oi,q Gi,q−1 · · · Gi,1 Oi,1 Gi,0 , 0 0 Ui0 = Gi,q Oi,q Gi,q−1 · · · Gi,1 Oi,1 Gi,0 .

(63)

Both act on the joint space Hi ⊗ Wi . Here Gi,0 , . . . , Gi,q are are common unitary operators, whereas 1 and O0 are the original and modified oracle query unitaries. The unitaries G may also Oi,j i,j i,j include identical oracle queries. Acceptance. space.

At location i ∈ [ N ], Let Ji be the isometry that appends zero workspace to an input Ji : Hi −→ Hi ⊗ Wi ,

Ji |ψ⟩ = |ψ⟩ |0⟩Wi .

Let Πi be an efficiently measurable final acceptance projector. The accepting maps for the original and modified computations are Ai = Πi Ui1 Ji ,

Ci = Πi Ui0 Ji .

(64)

Their acceptance probabilities on the local input ρi are Pr[original accepts] = Tr( Ai ρi Ai† ),

Pr[modified accepts] = Tr(Ci ρi Ci† ).

Witness at a position Let Qi be a computational-basis diagonal projector on the input register (i.e. on the Hilbert space Hi ) such that 1 0 (Oi,j − Oi,j )( I − Qi ) = 0

for every j ∈ [q].

(65)

Thus the two oracles agree on every query outside the support of Qi . A classical query input x is a witness at location i ∈ [ N ] if it is in the support of the projector Qi i.e, Qi | x ⟩ = | x ⟩ .

49

(66)

Remark 8.1. Let Ui,0< j be the unitary part of the modified computation before its jth query: Ui,0<1 = Gi,0 , 0 0 Ui,0< j = ( Gi,j−1 Oi,j −1 ) · · · ( Gi,1 Oi,1 ) Gi,0 ,

2 ≤ j ≤ q.

(67)

Appending the zero workspace providing isometry Ji , we also define Vi,j = Ui,0< j Ji

(68)

We assume that all of Ui,0< j , (Ui,0< j )† , Qi can be implemented efficiently, using only the oracles available to Ui0 . Sampling a witness. A witness sampler chooses an index j ∈ [q] uniformly, runs the modified computation up to that position, and measures its query input. It succeeds if the measured input is a witness, and fails otherwise. The effect describing the success probability of this sampler is q

1 Ei = ∑ Vi,j† Qi Vi,j , q j =1

0 ⪯ Ei ⪯ I.

(69)

In particular, Pr[the sampler outputs a witness on ρi ] = Tr( Ei ρi ). We note that, measuring a uniformly chosen oracle query is a standard extraction technique as done in [CMP24]. Here the sampler runs the modified computation. Filtering the input. On input components i ∈ [ N ], where the above witness sampling procedure succeeds with low probability, we will bound the probability of acceptance in the original experiment using that of the modified experiment. To do that, first fix an integer β ≥ 1 and define a filtering operator Li = ( I − Ei ) β . (70) For every unit eigenvector |e⟩ of Ei , Ei |e⟩ = u |e⟩

L i | e ⟩ = (1 − u ) β | e ⟩ ,

=⇒

u ∈ [0, 1].

Here u is the witness-sampling probability on |e⟩. The filter therefore suppresses components with large witness-sampling probability. The implementation follows the modified Marriott–Watrous procedure of [HLM17]. As shown in the proof, each successful cycle applies I − Ei , so β successful cycles implement the branch ρi 7−→ Li ρi Li . Acceptance probability after filtering for the modified experiment. Let ε β be the sum, over all locations i ∈ [ N ], of the probabilities that the filter Li succeeds and the modified computation then accepts: h  i N ε β = ∑ E Tr Ci Li ρi Li Ci† . (71) i =1

The expectation is over the distribution of the classical oracles. Now, we are ready to formally state the extraction lemma. 50

Lemma 8.2. Fix an integer β ≥ 1. Consider the original and modified q-query oracle aided computation as described in Equation (63). Let Xi indicate acceptance by the original computation at location i ∈ [ N ]. For every δ ∈ (0, 1), for every location i ∈ [ N ] there are local extracting procedures that output either a a witness (65,66) or a failure. If Yi indicates a successful witness output, then, for every d ∈ [ N ], " # " # N

N

i =1

i =1

Pr ∑ Xi ≥ d ≤ Pr ∑ Yi ≥ d + Nδ(2 + δ) 8Nq2 + (1 + δ−1 ) 2ε β + 2β + 1 

(72)

 .

The two probabilities refer to separate executions on the same input state ρ. Each witness extracting procedure receives only its local input and fresh workspace. It uses the the unitaries † Ui,0< j , Ui,0< j and witness testing projectors Qi , as in Remark 8.1, with no communication between separate locations. Moreover, the witness extraction procedure is QPT under the assumption of Remark 8.1 and polynomially bounded β, and 1/δ. Proof. We first work at one location and omit its index. 1. Comparing the two computations. We use the standard oracle-hybrid argument of [BBBV97], as in Lemma 3.2, written as an operator inequality. For each query position j, let Bj be the suffix unitary of the original computation after the j-th query: Bq = Gq ,

Bj = Gq Oq1 Gq−1 · · · O1j+1 Gj

(1 ≤ j < q ).

Replacing the queries (original and modified oracle queries) one at a time gives the telescoping identity q

A − C = ∑ ΠBj (O1j − O0j )Vj . j =1

Recall Vj is the prefix relative to the modified oracles defined as in Equation (68). By the witness condition (Equation (65)) and unitarity, we also have, O1j − O0j = (O1j − O0j ) Q,

O1j − O0j

≤ 2,

op

ΠBj op ≤ 1.

Consequently, for every input vector |ψ⟩, by triangle-inequality, 2

q

∥( A − C ) |ψ⟩∥ ≤ 4

∑ QVj |ψ⟩

!2

j =1 q

≤ 4q ∑ QVj |ψ⟩

2

= 4q2 ⟨ψ| E |ψ⟩ .

j =1

The second inequality is Cauchy–Schwarz and the final equality is due the definition of the operator E as in Equation (69). Since this is true for all unit vector |ψ⟩,

( A − C )† ( A − C ) ⪯ 4q2 E.

51

(73)

2. Implementing the filter. We construct a procedure whose successful branch applies the operator I − E on the input register. Repeating it β times, we will implement the filter operator L = ( I − E) β . The filter follows the modified Marriott–Watrous procedure of Harrow, Lin, and Montanaro [HLM17]. For this purpose, we first implement the witness sampling experiment coherently. Let R be a register of log2 q qubits, with computational-basis states labelled by j ∈ [q]. Let J0 append both R and the circuit workspace W in their zero states: J0† J0 = I.

J0 |ψ⟩ = |0⟩ R J |ψ⟩ = |0⟩ R |ψ⟩ |0⟩W ,

0 J, where U 0 is the unitary part of the modified computation We recall from Remark 8.1 Vj = U< j <j before query j. 0 controlled on its value j, without measuring R. Apply Hadamards on R and then apply U< j Let, the resulting joint unitary is V. It satisfies q

q

1 1 0 V J0 |ψ⟩ = √ ∑ | j⟩ R U< j J | ψ ⟩ = √ ∑ | j ⟩ R Vj | ψ ⟩ . q j =1 q j =1 Under the assumption of Remark 8.1, we note that both V and V † have efficient implementation. Now, On the enlarged space, define the projector Π0 = J0 J0† = |0⟩⟨0| R ⊗ I ⊗ |0⟩⟨0|W ,

ΠQ = IR ⊗ Q.

(74)

The projector Π0 checks whether both appended registers are zero, leaving the input register unrestricted. The projector ΠQ tests the witness condition on the query input and acts identically on R. Combining the operators, we have the following important identity: q

J0† V † ΠQ V J0 =

q

1 1 ⟨k| j⟩ Vk† QVj = ∑ Vj† QVj = E ∑ q k,j=1 q j =1

(75)

Also, Π0 V † ( I − ΠQ )V J0 = J0 ( I − E)

(76)

The last identity follows from Π0 = J0 J0† , V † V = I, and J0† J0 = I. We are now ready to describe the filter operator. One filter cycle consists of the following operations. (i) Apply J0 . (ii) Apply V and measure {ΠQ , I − ΠQ }. Continue only on outcome I − ΠQ . (iii) Apply V † and measure {Π0 , I − Π0 }. Continue only on outcome Π0 . Every other outcome is failure. By (75), the (unnormalized) vector after one successful cycle is Π0 V † ( I − ΠQ )V J0 |ψ⟩ = J0 ( I − E) |ψ⟩ . Since the appended registers are again zero, the same cycle can be repeated on the remaining input. After β successful cycles, the (unnormalized) vector is
J0 ( I − E) β |ψ⟩ = J0 L |ψ⟩ = |0⟩ R L |ψ⟩ |0⟩W . In particular, for a unit eigenvector E |e⟩ = u |e⟩, Pr[all β filter cycles succeed on |e⟩] = ∥ J0 L |e⟩∥2 = ∥ L |e⟩∥2 = (1 − u)2β . 52

3. Bounding acceptance after filtering. We will compare the acceptance probabilities of the original and modified computation on the filtered input. Their successful maps are AL and CL, respectively. We first bound their difference ( A − C ) L. Since L = ( I − E) β is Hermitian and commutes with E, (73) gives L( A − C )† ( A − C ) L ⪯ 4q2 LEL = 4q2 E( I − E)2β . The eigenvalues of E( I − E)2β are u(1 − u)2β , where u ∈ [0, 1] ranges over the eigenvalues of E. This scalar function is maximized at u = 1/(2β + 1), so u (1 − u )

2β

1 ≤ 2β + 1



2β 2β + 1

2β

≤

1 . 2β + 1

Consequently, L( A − C )† ( A − C ) L ⪯

4q2 I. 2β + 1

Now decompose AL = CL + ( A − C ) L. Using ∥ x + y∥2 ≤ 2 ∥ x ∥2 + 2 ∥y∥2 , for every input vector |ψ⟩ we obtain

∥ AL |ψ⟩∥2 ≤ 2 ∥CL |ψ⟩∥2 + 2 ∥( A − C ) L |ψ⟩∥2 ≤ 2 ∥CL |ψ⟩∥2 +

8q2 ∥|ψ⟩∥2 . 2β + 1

Since this holds for every |ψ⟩, it is equivalent to LA† AL ⪯ 2LC † CL +

8q2 I. 2β + 1

(77)

Restoring the location indices, the same bound applies to each local mixed input ρi : Tr( Ai Li ρi Li Ai† ) ≤ 2 Tr(Ci Li ρi Li Ci† ) +

8q2 Tr ρi . 2β + 1

The two trace terms are the probabilities of successful filtering followed by acceptance for the original and modified computation, respectively. Finally, Tr ρi ≤ 1. Taking expectation over the oracle distributions, summing over all locations, and using the definition of ε β in (71), we obtain N

h

i

8Nq2

∑ E Tr( Ai Li ρi Li Ai† ) ≤ 2ε β + 2β + 1 .

(78)

i =1

4. The witness extraction procedure. We now construct a witness extractor on the original local input. Its purpose is to find a witness with high probability on the components strongly suppressed by the filter L. Consider the projectors Π0 , ΠQ from Equation (74). On the enlarged space, define the projector and the parameter   2β † † S = VΠ0 V = (V J0 )(V J0 ) , T = ΠQ , t= . δ2 53

Since V J0 is an isometry H → H ⊗ W , S is the orthogonal projector onto the image of the map V J0 . The projector T tests whether the current query input is a witness. After rejection by T, the state is supported in the range of I − T. An immediate repetition of the witness test would therefore reject again, since T ( I − T ) = 0. We interleave witness tests with measurements of S, which can kickback some nonzero weight in the witness subspace. Use the following alternating-projector procedure, based on Marriott–Watrous amplification [MW05]. (i) Append zero registers using J0 , apply V, and measure { T, I − T }. (ii) Whenever the witness test accepts, measure the complete query input in the computational basis, output it, and stop. (iii) After the first rejection, perform at most t further rounds. In each round, measure {S, I − S}, discard that outcome, and then measure { T, I − T }. On acceptance, output the query as above. If every witness test rejects, output failure. Both outcomes of the S-measurement lead to the next witness test; neither outcome causes the procedure to abort. 5. Computing the extraction probability. By Jordan’s lemma, the sampler space decomposes into mutually orthogonal subspaces of dimension at most two that are invariant under both S and T [NWZ09; CMSZ21]. We include the standard two-projector calculation for completeness [NWZ09; CMSZ21]. It gives the exact extraction probability, which we then use to compare the success effect W with ( I − L)2 . Fix a unit eigenvector E |e⟩ = u |e⟩ with 0 < u < 1, and let

|v⟩ = V J0 |e⟩ Since V J0 is an isometry and J0† V † TV J0 = E, by Equation (75), we have

∥ T |v⟩∥2 = u,

∥|v⟩∥ = 1,

∥( I − T ) |v⟩∥2 = 1 − u.

Thus the normalized states after witness acceptance and rejection are, respectively, T |v⟩ |w⟩ = √ , u

|z⟩ =

( I − T ) |v⟩ √ . 1−u

These vectors are orthogonal and

|v⟩ =

√

u |w⟩ +

√

1 − u |z⟩ .

To determine how the S-measurement changes these states, use S = (V J0 )(V J0 )† to obtain S |v⟩ = |v⟩ , It follows that

ST |v⟩ = V J0 E |e⟩ = u |v⟩ .

√

q u | v ⟩ = u | w ⟩ + u (1 − u ) | z ⟩ , q √ S | z ⟩ = 1 − u | v ⟩ = u (1 − u ) | w ⟩ + (1 − u ) | z ⟩ .

S |w⟩ =

Hence the two-dimensional space Ke = span{|w⟩ , |z⟩} is invariant under S, T. In the ordered basis (|w⟩ , |z⟩), their restrictions are p     u 1 0 u (1 − u ) p T K = , SK = . (79) e e 0 0 u (1 − u ) 1−u 54

The first witness test succeeds with probability u. On rejection, the normalized state is |z⟩. In the next round, the two possible S-outcomes followed by witness acceptance give the (unnormalized) vectors q q TS |z⟩ =

u (1 − u ) | w ⟩ ,

T ( I − S) |z⟩ = −

u (1 − u ) | w ⟩ .

Since these branches correspond to distinct measured outcomes of {S, I − S}, their probabilities add. Thus one further round succeeds with probability

∥ TS |z⟩∥2 + ∥ T ( I − S) |z⟩∥2 = 2u(1 − u). If the witness test rejects again, the normalized state returns to |z⟩. Consequently, each further round, conditioned on all earlier rejections, fails with probability 1 − 2u(1 − u). Including the initial rejection and the t further rounds, the total witness extraction probability is gt (u) = 1 − (1 − u)[1 − 2u(1 − u)]t . (80) We note that, for u = 0, every witness test rejects; for u = 1, the first accepts. These endpoint cases agree with gt (0) = 0 and gt (1) = 1. To extend this calculation to arbitrary inputs, choose an orthonormal eigenbasis {|ek ⟩}k of E, with eigenvalues uk , and write |vk ⟩ = V J0 |ek ⟩. For k ̸= ℓ,

⟨ Tvk , Tvℓ ⟩ = ⟨ek | E |eℓ ⟩ = 0, ⟨( I − T )vk , ( I − T )vℓ ⟩ = ⟨ek | ( I − E) |eℓ ⟩ = 0. Therefore, the spaces span{ T |vk ⟩ , ( I − T ) |vk ⟩} are mutually orthogonal and invariant under S and T. Every sequence of these measurements preserves the spaces, so distinct eigenvector components contribute without interference to the success probability. For a unit input vector |ψ⟩ = ∑k ck |ek ⟩, Pr[extract a witness on |ψ⟩] = ∑ |ck |2 gt (uk ). k

Thus the witness procedure has success effect 0 ⪯ W ⪯ I.

W = gt ( E ),

That is, its probability of outputting a witness on an input state ρ is Tr(Wρ). We next control A( I − L) in the decomposition A = A( I − L) + AL. The term corresponding to AL is bounded by (77). For the other term, since A = ΠU 1 J ⪯ I is a contraction,
† A ( I − L ) A ( I − L ) = ( I − L ) A † A ( I − L ) ⪯ ( I − L )2 . We will show that ( I − L)2 ⪯ W + δI. This will bound the squared norm of A( I − L) |ψ⟩ by the witness-extraction probability on |ψ⟩, up to δ ∥|ψ⟩∥2 . Both W = gt ( E) and L = ( I − E) β are functions of E. For each eigenvector E |e⟩ = u |e⟩, W | e ⟩ = gt ( u ) | e ⟩ ,

( I − L )2 | e ⟩ = [1 − (1 − u ) β ]2 | e ⟩ . 55

Thus W − ( I − L)2 + δI is diagonal in an orthonormal eigenbasis of E, with eigenvalues gt (u) − [1 − (1 − u) β ]2 + δ. To prove that this operator is positive semidefinite, it therefore suffices to show that these scalar quantities are nonnegative. Split the eigenvalue range at δ . α= 2β Since t = ⌈2β/δ2 ⌉, tα ≥

2β δ 1 = . 2 δ 2β δ

For u ≥ α, we bound the extraction failure probability. Using (80) and 1 − x ≤ e−x , 1 − gt (u) = (1 − u)[1 − 2u(1 − u)]t

≤ (1 − u)e−2tu(1−u) ≤ (1 − u)e−2tα(1−u) 1 ≤ δ. ≤ 2e tα The penultimate inequality applies xe−ax ≤ 1/(ea) with x = 1 − u and a = 2tα. Hence gt (u) ≥ 1 − δ throughout this range. For 0 ≤ u < α, it is enough to bound the comparison term. Bernoulli’s inequality gives

(1 − u) β ≥ 1 − βu,

0 ≤ 1 − (1 − u) β ≤ βu.

Consequently,

[1 − (1 − u ) β ]2 ≤ β2 u2 ≤ β2 α2 =

δ2 ≤ δ. 4

For u ≥ α, use gt (u) ≥ 1 − δ and [1 − (1 − u) β ]2 ≤ 1. For u < α, use gt (u) ≥ 0 and the bound just established. Together these give gt (u) − [1 − (1 − u) β ]2 + δ ≥ 0,

u ∈ [0, 1].

Every eigenvalue of W − ( I − L)2 + δI is therefore nonnegative, proving W ⪰ ( I − L)2 − δI.

(81)

6. Comparing acceptance with extraction. We compare the original acceptance effect A† A with the witness success effect W, keeping the contribution of filtered acceptance explicit. For every input vector, A |ψ⟩ = A( I − L) |ψ⟩ + AL |ψ⟩ . These two terms need not be orthogonal. The weighted Cauchy–Schwarz inequality bounds their cross term and gives

∥ A |ψ⟩∥2 ≤ (1 + δ) ∥ A( I − L) |ψ⟩∥2 + (1 + δ−1 ) ∥ AL |ψ⟩∥2 .

56

Since L† = L and the inequality holds for every |ψ⟩, we obtain A† A ⪯ (1 + δ)( I − L) A† A( I − L) + (1 + δ−1 ) LA† AL

⪯ (1 + δ)( I − L)2 + (1 + δ−1 ) LA† AL. The second line uses A† A ⪯ I. The extraction bound (81) gives

( I − L)2 ⪯ W + δI. Substituting this bound yields, A† A ⪯ (1 + δ)W + δ(1 + δ) I + (1 + δ−1 ) LA† AL

=⇒ A† A − W ⪯ δW + δ(1 + δ) I + (1 + δ−1 ) LA† AL

(82)

⪯ δ(2 + δ) I + (1 + δ−1 ) LA† AL. Here LA† AL is the effect of successful filtering followed by original acceptance. Its total contribution over the locations is bounded by (78). 7. Comparing the joint success thresholds. We now use the local comparison (82) to compare the probabilities of at least d original acceptances and at least d witness outputs on the joint input ρ. For local success effects 0 ⪯ Zi ⪯ I, the effects of success and failure at location i are Zi and I − Zi , respectively. Thus the joint outcome z = (z1 , . . . , z N ) ∈ {0, 1} N has effect N O

Zizi ( I − Zi )1−zi .

i =1

Summing the outcomes with at least d successes gives the threshold effect Td ( Z1 , . . . , ZN ) =

∑

N O

Zizi ( I − Zi )1−zi .

(83)

z∈{0,1} N i =1 ∑i zi ≥ d

Thus, Pr[at least d successes] = Tr( Td ( Z1 , . . . , ZN )ρ) . We replace the original tests by the witness extracting tests one location at a time. For 0 ≤ i ≤ N, define Fi = Td (W1 , . . . , Wi , Ai†+1 Ai+1 , . . . , A†N A N ). Thus Fi uses witness extraction at locations 1, . . . , i and original acceptance at locations i + 1, . . . , N. In particular, F0 = Td ( A1† A1 , . . . , A†N A N ), FN = Td (W1 , . . . , WN ). Now, fix a particular step i ∈ [ N ]. Only the test at location i changes between Fi−1 and Fi . For this comparison, we consider the unchanged effects at all other locations as ( Wj , j < i, Zj = † A j A j , j > i. 57

Changing the outcome at location i affects the global threshold d only when the other locations have exactly d − 1 successes. Because, with at least d other successes the threshold is already met, while with at most d − 2 it cannot be met by either local outcome. Define the effect of exactly d − 1 successes among the other locations by

∑

Gi =

O

(z j ) j̸=i ∈{0,1} N −1 j̸=i ∑ j ̸ =i z j = d −1

z

Z j j ( I − Z j )1− z j .

Let Hi be the effect of at least d successes among those same locations, i,e,

∑

Hi =

O

(z j ) j̸=i ∈{0,1} N −1 j̸=i ∑ j ̸ =i z j ≥ d

z

Z j j ( I − Z j )1− z j .

The global threshold d is met either through the event represented by Hi , regardless of the local outcome, or through the event represented by Gi together with a local success at i. Consequently, with identity factors implicit, Fi−1 = Hi + ( Ai† Ai ) Gi , Fi = Hi + Wi Gi . Subtracting the common contribution Hi we get: Fi−1 − Fi = ( Ai† Ai − Wi ) Gi . Summing the consecutive differences cancels all intermediate effects F1 , . . . , FN −1 , giving Td ( A1† A1 , . . . , A†N A N ) − Td (W1 , . . . , WN ) N

= F0 − FN = ∑ ( Fi−1 − Fi )

(84)

i =1

N

= ∑ ( Ai† Ai − Wi ) Gi . i =1

Since Gi ⪰ 0 acts outside location i, tensoring the local comparison by Gi preserves operator order. Thus (82) gives

( Ai† Ai − Wi ) Gi ⪯ δ(2 + δ) Gi + (1 + δ−1 ) Li Ai† Ai Li Gi ⪯ δ(2 + δ) I + (1 + δ−1 ) Li Ai† Ai Li . For the second line, use Gi ⪯ I. Combining these bounds with (84), we obtain N

F0 − FN ⪯ Nδ(2 + δ) I + (1 + δ−1 ) ∑ Li Ai† Ai Li . i =1

Now, taking the trace against ρ (note, Tr ρ ≤ 1), and taking expectation over over the oracle distributions, we get " # E[Tr( F0 ρ)] = Pr ∑ Xi ≥ d , i

"

#

E[Tr( FN ρ)] = Pr ∑ Yi ≥ d . i

58

we therefore obtain "

#

"

#

Pr ∑ Xi ≥ d − Pr ∑ Yi ≥ d ≤ Nδ(2 + δ) i

i

h i N + (1 + δ−1 ) ∑ E Tr( Ai Li ρi Li Ai† ) . i =1

Finally, this along with the bound established in (78) proves (72). We also note that, each local extractor performs one initial witness test and at most t = ⌈2β/δ2 ⌉ additional rounds. The implementations of V, V † , and the witness test therefore give the claimed polynomial complexity under the assumption of Remark 8.1.

8.2

From cloning to torch signatures

We now apply Lemma 8.2 to prove global non-proliferation for Construction 7.4. Write si = (ℓi , ai ) for the serial of the challenge flame issued to location i after the split in the global non-proliferation experiment as in Definition 6.2 of the torch-fire object. We call ℓi ∈ {0, 1}λ the challenge label: it selects the anchor source O A,ℓi , while ai is the anchor’s verification key within that source ((38)). Recall that each flame contains an anchor and a CGS part ((40)). Successful cloning therefore requires two anchors that pass the test under ai ((48)). The proof uses the two OSS schemes as follows. (i) Disable affine access to the anchor source O A,ℓi . We show that successful filtering followed by two accepted anchors would give a strong one-bit OSS forgery (Theorem 4.11). This bounds the 2ε β term in (72). (ii) Every query whose answer changes under this oracle disabling modification contains a valid torch signature (Construction 7.3). Its signed message includes ℓi . We then show that obtaining such signatures for m + 1 distinct challenge labels from only m issued torches would violate long-message OSS security (Theorem 4.14). The extraction Lemma 8.2 connects these two steps even when the locations share entanglement. We first define the modified oracle and the witness queries. The local input and acceptance test. Let ρ be the joint state of the local inputs B1 F1 , . . . , BN FN at the start of the global non proliferation experiment as in Definition 6.2 of the torch-fire object. Let ρi be its reduced state on Bi Fi . Due to setup aborts and label collisions, assume ρ may be subnormalized. For the operator definitions below, fix the classical oracle functions and public inputs pk, s1 , . . . , s N , where si = (ℓi , ai ). All the expectation calculations below average over their distributions. At location i, let Ui1 coherently run AiO on Bi Fi , followed by verification of both output flames under si . Retain the workspace and measurement records as in Fact 3.1. Let Ji append zero workspace, and let Πi test that both verifications accept. Thus h i Ai = Πi Ui1 Ji , Pr[ Xi = 1] = E Tr( Ai ρi Ai† ) . We implement the anchor verification tests by the Hadamard-dual-Hadamard test as in Lemma 4.8 which corresponds to the projector Π ai = | A ai ⟩⟨ A ai |, 59

Removing the challenge label’s affine access. Now we define the modified version of the computation as in Equation (63). The modified computation uses the same oracles except that Γ returns ⊥ on every affine request carrying ℓi . For a well-formed request q′ = (s′ , t, c, e, u), with s′ = (ℓ′ , a′ ), define ( ⊥, ℓ ′ = ℓi , 0 ′ Γi (q , p, σA , σT ) = (85) Γ(q′ , p, σA , σT ), ℓ′ ̸= ℓi . Malformed inputs also return ⊥. Write Oi0 for the public collection obtained by this replacement, and let Ui0 be the mofied version of Ui1 with access to Oi0 . Its accepting map is Ci = Πi Ui0 Ji . The witness in a distinguishing query. For the two affine oracles to differ, the original oracle must answer a request carrying ℓi . By (45), such a request must include a valid signature under a published torch key. We therefore let Qi be the computational-basis diagonal projector onto complete Γ-query inputs satisfying q′ = (s′ , t, c, e, u) ∈ Qaffine , t ∈ Tpub ,

s′ = (ℓi , a′ ),
OSS.VerOT t, MT (s′ , t), σT = 1.

(86)

Set Qi = 0 on malformed inputs and designated padding queries. The predicate is coherently testable using T and public torch OSS verification, both available in Oi0 . Outside the support of Qi , either the request has a different label, or both affine oracles reject it. Consequently, (UΓ − UΓ0 )( I − Qi ) = 0, (87) i

which is precisely the witness condition of Lemma 8.2. Crucially, The predicate need not check the anchor signature or the CGS tag ((45)). Those checks are necessary for a affine response, but the reduction needs only the torch signature. Thus a witness may satisfy Qi even when Γ rejects it. Measuring a witness and retaining its torch-signature fields gives
t ∈ Tpub , (88) s′ = (ℓi , a′ ), t, MT (s′ , t), σT , with a valid signature under t. The key a′ need not equal the challenge key ai : the relevant information is the label ℓi . Indeed, (43) gives MT (s′ , t) = 1∥ℓi ∥ a1′ ∥ · · · ∥ a′L ∥t1 ∥ · · · ∥t L . These messages have length 1 + λ + 2Lr. Distinct challenge labels therefore give distinct signed messages, including when the witnesses use the same torch key. The quantity left to bound. Choose a common power-of-two bound q ≥ 1 on the local Γ-query positions, padding with invalid queries. All other oracle queries are identical in Ui1 and Ui0 . For the modified prefixes Vi,j = Ui,0< j Ji , define q

Ei =

1 Vi,j† Qi Vi,j , q j∑ =1

Li = ( I − Ei ) β ,

60

β ≥ 1,

as in Section 8.1. Consider, the error term in the extraction Lemma 8.2 is i h N ε β = ∑ E Tr(Ci Li ρi Li Ci† ) . i =1

Each summand includes both successful filtering and acceptance by the modified computation. We will bound it by anchor OSS security, then use torch OSS security to bound the number of successful witness outputs. Why the preparation phase must also be modified. The input ρ was prepared before the split in the experiment Definition 6.2 using the original oracle Γ. It could therefore already contain information obtained from the affine queries that Ui0 later disables. To use anchor OSS security, we must remove that access from the preparation phase as well. The challenge label is uniform and unknown during this phase; the next lemma bounds the effect of the additional replacement. Lemma 8.3. Fix i ∈ [ N ]. Replace Γ by Γ0i also before the split in th experiment Definition 6.2, keeping the other oracles and honest issuance unchanged. Let ρei be the resulting joint input state after challenge issuance and the experiment’s abort checks. For every effect 0 ⪯ Z ⪯ I on the joint input, possibly depending on the classical oracle functions and public inputs, ρi )]| ≤ 2Qpre 2−λ/2 . |E[Tr( Zρ)] − E[Tr( Ze

(89)

Here Qpre is the pre-split query bound fixed at the start of Section 8. The subscript on ρei specifies which label’s affine queries are disabled; this is a state of all locations. Proof. Fix the oracle functions. Sample ℓi ← {0, 1}λ before running A0 , keeping it secret until challenge issuance, and defer the label-collision checks. Let ω j be the query-register state immediately before the j-th query in the original pre-split execution. These states are independent of ℓi . Let Πaffine project onto Γ-query inputs carrying label ℓ. Since ∑ℓ Πaffine ⪯ I, the total query ℓ ℓ mass at the hidden label satisfies Qpre

Mℓi := ∑ Tr(Πaffine ω j ), ℓi j =1

Qpre

E ℓ i [ Mℓ i ] = 2

−λ

∑ Tr

"

j =1

∑

! Πaffine ℓ

# ω j ≤ Qpre 2−λ .

ℓ

By (85),

(UΓ − UΓ0 )( I − Πaffine ) = 0, ℓi i

and all other oracles are unchanged. Thus, writing τ 1 , τi0 for the two pre-split states, Lemma 3.2 and Jensen’s inequality give q h i hq i 1 0 Eℓi D (τ , τi ) ≤ 2 Qpre Eℓi Mℓ i q ≤ 2 Qpre Eℓi [ Mℓi ]

≤ 2Qpre 2−λ/2 .

61

Applying the common challenge-issuance and collision-check, recording aborts as failure and extending Z by zero on failure, we have ρi )| ≤ ED (τ 1 , τi0 ) ≤ 2Qpre 2−λ/2 , |E Tr( Zρ) − E Tr( Ze where E also averages over the oracle functions. This proves (89) without conditioning on nonabort. We now bound the 2ε β term in (72) using anchor OSS security. The reduction runs the filter followed by the modified computation, counting filter failures as failures of the reduction. Two accepted anchors will then provide a strong one-bit OSS forgery. Lemma 8.4. For every polynomially bounded integer β ≥ 1, h i N ε β = ∑ E Tr( Li Ci† ρi Ci Li ) ≤ negl(λ),

(90)

i =1

where local operators act as the identity on all other locations. Proof. We construct a strong one-bit OSS forger in the following way. 1. Disable the affine queries during preparation. The reduction must also avoid the challenge label’s private affine queries before the split. Since Ci is a contraction and 0 ⪯ Li ⪯ I, Zi := Li Ci† Ci Li ,

0 ⪯ Zi ⪯ L2i ⪯ I.

Thus Lemma 8.3, applied to Zi , gives pi := E[Tr( Zi ρei )] , N

(91)

ε β ≤ ∑ pi + 2NQpre 2−λ/2 . i =1

We construct an OSS forger whose success probability is proportional to ∑i pi . 2. Set up the OSS reduction.

In the OSS game of Theorem 4.11, the challenger COSS samples

O ⋆ ← OSS.GenOracles(1λ ) and gives the forger BA access to its public oracles. The forger attacks this source by running the torch-fire adversary A in the modified experiment. The forger chooses i ← [ N ] uniformly and secretly samples ℓi ← {0, 1}λ . It answers public oracle queries addressed to anchor component (ℓi , 1) using O ⋆ . It samples the torch source O T , the CGS source OK , all other anchor components, and the remaining construction data as prescribed by Construction 7.4. Since the anchor components are independent one-bit OSS sources, this gives the prescribed joint distribution of the underlying sources. The adversary receives Γ0i from (85) throughout the experiment: requests carrying ℓi return ⊥, and all other affine responses and checks are computed from the sources sampled by BA . For the first component of the challenge anchor, the forger runs ⋆

(y, |Wy ⟩) ← OSS.GenQKeyO (1λ ),

ai,1 := y.

By Construction 4.6, this produces the required uniform verification key and signing state using public oracle queries. The remaining challenge components and honest issuances use the sampled sources. Taking into account the abort possibilities, the resulting joint input is ρei . 62

3. Run the filter and the modified computation. At the chosen location, BA runs Li , then Ui0 and the acceptance test Πi . The joint successful branch has map Ci Li , and hence probability h i † e pi = E Tr(Ci Li ρi Li Ci ) . By Remark 8.1 and (86), the complete reduction makes polynomially many queries to O ⋆ for polynomial β. 4. Forge under the challenged OSS source. Retain the two output anchor registers after their projective tests. By Lemma 4.8 and (48), the accepting map on each anchor is the rank-one projector Π ai = | A ai ⟩⟨ A ai | . The joint successful state therefore has the form

| A ai ⟩⟨ A ai | A(0) ⊗ | A ai ⟩⟨ A ai | A(1) ⊗ τ,

τ ⪰ 0,

E[Tr(τ )] = pi .

For fixed source data and y = ai,1 , measuring component 1 of each anchor gives independent uniform samples u0 , u1 ∈ Wy . Thus Pr[u0 ̸= u1 | joint success] = 1 −

1 = 1 − 2−(n−r) . |Wy |

When u0 ̸= u1 , the forger returns to COSS the key and signature pairs

( u1 )1 , u1 . y, ( u0 )1 , u0 , These are signatures for the source sampled by the OSS challenger: by (9),
⋆ OSS.VerO y, (ub )1 , ub = 1 (b ∈ {0, 1}). The pairs are distinct because u0 ̸= u1 , even if their message bits coincide. The strong OSS game in Theorem 4.11 permits the forger to output this key y. For each chosen location, the forging probability is (1 − 2−(n−r) ) pi . Averaging over i ← [ N ] gives 1 − 2−(n−r) N Pr[BA forges] = ∑ pi ≤ negl(λ), N i =1 where the inequality follows from Theorem 4.11. Finally, (91) and n − r = 24λ yield N Pr[BA forges] + 2NQpre 2−λ/2 1 − 2−24λ ≤ negl(λ),

εβ ≤

since N and Qpre are polynomially bounded. We now bound the witness extraction probability term in (72) at threshold m + 1. Distinct labels give distinct torch messages by (43). Among m + 1 witnesses, either two use the same key of an issued torch, or one uses a key whose torch was not issued.

63

Lemma 8.5. Let AW be a quantum procedure following the global non-proliferation experiment’s (Definition 6.2) issuance rules, receiving only the m issued torch registers, and making polynomially many public-oracle queries. For witnesses defined by (88),   AW outputs valid witnesses ≤ negl(λ). pwit := Pr for m + 1 distinct labels The procedure may process all pre-split and challenge flames jointly. Proof. If R = 0, then Tpub = ∅, so no witness is valid. Assume R ≥ 1. We construct a long-message OSS forger BT using AW . 1. Simulate setup and issuance.

The OSS challenger COSS samples

O ⋆ ← OSS.GenOracles(1λ ) for the long-message scheme of Construction 4.13, and gives BT access to its public oracles. The forger answers simulated torch-source queries using O ⋆ , and samples all anchor and CGS sources as prescribed by Construction 7.4. Its target is a forgery under O ⋆ . To generate the published torches, BT runs ⋆

(t j , Tj ) ← OSS.GenQKeyO (1λ ),

j ∈ [ R ].

By Constructions 4.6 and 4.13, for each fixed source the keys are independent and uniform in ({0, 1}r ) L , and their corresponding signing state is ρ T1 ···TR =

R O

| Tt j ⟩⟨ Tt j | .

j =1

This is the setup distribution of Construction 7.4, obtained here without tdT . Publish the keys through T as in (36). For the selected set J ⊆ [ R], | J | = m, give AW precisely the registers ( Tj ) j∈ J and retain ( Tj ) j/∈ J . Generate all flames from the sampled anchor and CGS sources. The oracle Γ uses the challenged source only for the public torch-verification test in (45); its remaining checks and affine responses use the sampled data. 2. Turn the witnesses into a forgery. On witness success, retain m + 1 witnesses with distinct labels ℓ1 , . . . , ℓm+1 . Write their signature fields as

(t jh , Mh , σh ),

jh ∈ [ R ] ,

h ∈ [ m + 1].

Witness validity and (43) give ⋆

OSS.VerO (t jh , Mh , σh ) = 1, h ̸= k

=⇒

ℓh ̸= ℓk

=⇒

M h ̸ = Mk .

The forger proceeds as follows. (i) Every jh belongs to J. Since | J | = m, there are h ̸= k with jh = jk =: j. Return to the OSS challenger tj, ( Mh , σh ), ( Mk , σk ). Both signatures verify under the same key, and Mh ̸= Mk . 64

(ii) Some jh does not belong to J. Choose such an h and put j := jh . Using the retained register Tj , compute ⋆ M⋆ := 0 1+λ+2Lr , σ⋆ ← OSS.SignO (t j , Tj , M⋆ ). By (43), Mh starts with 1, so M⋆ ̸= Mh . Return tj,

( Mh , σh ),

( M⋆ , σ⋆ ).

This is a forgery whenever σ⋆ verifies. Both cases attack the source sampled by COSS . The OSS game of Theorem 4.14 permits the forger to output the selected verification key t j . 3. Bound the final signing error. The bound eT in (50) holds for every published key and message, so it applies also to the untouched torch selected from the witnesses in case (ii). Since case (i) always yields a forgery, pwit ≤ Pr[BT forges] + E[eT ]

≤ negl(λ) + negl(λ) ≤ negl(λ),

8.3

Global non-proliferation

We now combine the two reductions with the threshold guarantee of Lemma 8.2. The anchor reduction makes its filtered-acceptance error negligible. The torch reduction rules out m + 1 extracted witnesses with distinct labels. Theorem 8.6 (Global non-proliferation). Construction 7.4 satisfies Definition 6.2. For polynomially bounded R, m, N, with 0 ≤ m ≤ R, and every adversary allowed in that definition, i h λ R ( 1 , 1 , m, N ) = 1 ≤ negl(λ). (92) Pr SPLITTF O A Proof. If m ≥ N, the winning event is empty. Assume m < N. 1. Apply extraction to the ideal experiment (Equation (62)). Let # " N

pideal = Pr ∑ Xi ≥ m + 1 . i =1

For parameters β ≥ 1 and δ ∈ (0, 1), apply Lemma 8.2 to the computations and witnesses defined in Section 8.2. Let Yi indicate that the extractor at location i outputs a witness, and put # " N

pext = Pr ∑ Yi ≥ m + 1 . i =1

The extraction Lemma 8.2 gives pideal ≤ pext + Nδ(2 + δ)   8Nq2 −1 + (1 + δ ) 2ε β + . 2β + 1 Note, it does not require the local cloning or extraction outcomes to be independent. 65

(93)

2. Bound the extraction event by torch OSS security. The ideal experiment enforces distinct challenge labels, and Yi = 1 supplies a valid witness for ℓi by (88). Thus N

{ℓi : Yi = 1} = ∑ Yi , i =1

so m + 1 extraction successes give witnesses for m + 1 distinct labels. Applying Lemma 8.5 gives " # N

pext = Pr ∑ Yi ≥ m + 1 ≤ negl(λ). i =1

3. Choose the extraction parameters. δ=

Fix any integer c ≥ 1 and set 1 , 2Nλc

  β = N 2 q2 λ2c .

(94)

For this fixed c, Step 2 and Lemma 8.4 make pext + 2(1 + δ−1 )ε β negligible. Therefore, (93) gives pideal ≤ negl(λ) + Nδ(2 + δ) + (1 + δ−1 )

8Nq2 2β + 1

≤ negl(λ) + O(λ−c ). Since c is arbitrary and pideal is independent of the extraction parameters, pideal is negligible. 4. Return to the real experiment. The ideal experiment differs from the real one only by declaring failure on repeated spark labels. By (62),   v + N −λ preal ≤ pideal + ∆lab , ∆lab = 2 . 2 Both terms are negligible for polynomially bounded v, N. This proves (92).

Acknowledgments AM is supported by the National Research Foundation, Singapore, through the National Quantum Office, hosted in A*STAR, under its National Quantum Scholarship Scheme (NQSS) Funding Initiative (PhD).

66

References [Aar09]

Scott Aaronson. “Quantum Copy-Protection and Quantum Money”. In: CCC. 2009, pp. 229–242 (cit. on p. 3).

[AC12]

Scott Aaronson and Paul Christiano. “Quantum money from hidden subspaces”. In: STOC. 2012, pp. 41–60 (cit. on pp. 3, 21).

[AC23]

Ghada Almashaqbeh and Rohit Chatterjee. “Unclonable Cryptography: A Tale of Two No-Cloning Paradigms”. In: SECRYPT. 2023, pp. 469–477 (cit. on p. 3).

[AGKZ20]

Ryan Amos, Marios Georgiou, Aggelos Kiayias, and Mark Zhandry. “One-shot signatures and applications to hybrid quantum/classical authentication”. In: STOC. 2020, pp. 255–268 (cit. on pp. 3, 4, 7, 19).

[AHU19]

Andris Ambainis, Mike Hamburg, and Dominique Unruh. “Quantum Security Proofs Using Semi-classical Oracles”. In: CRYPTO. 2019 (cit. on pp. 7, 13, 14).

[AK21]

Prabhanjan Ananth and Fatih Kaleoglu. “Unclonable encryption, revisited”. In: Theory of Cryptography Conference. Springer. 2021, pp. 299–329 (cit. on p. 3).

[AKLLZ22]

Prabhanjan Ananth, Fatih Kaleoglu, Xingjian Li, Qipeng Liu, and Mark Zhandry. “On the Feasibility of Unclonable Encryption, and More”. In: CRYPTO. 2022 (cit. on pp. 7, 15).

[AKNYY23]

Shweta Agrawal, Fuyuki Kitagawa, Ryo Nishimaki, Shota Yamada, and Takashi Yamakawa. “Public Key Encryption with Secure Key Leasing”. In: EUROCRYPT. 2023 (cit. on p. 7).

[AKY25]

Prabhanjan Ananth, Fatih Kaleoglu, and Henry Yuen. “Simultaneous Haar Indistinguishability with Applications to Unclonable Cryptography”. In: ITCS. 2025 (cit. on pp. 7, 15).

[AL21]

Prabhanjan Ananth and Rolando L. La Placa. “Secure Software Leasing”. In: EUROCRYPT. 2021 (cit. on pp. 3, 7).

[ALLZZ21]

Scott Aaronson, Jiahui Liu, Qipeng Liu, Mark Zhandry, and Ruizhe Zhang. “New Approaches for Quantum Copy-Protection”. In: CRYPTO. 2021 (cit. on p. 3).

[APV23]

Prabhanjan Ananth, Alexander Poremba, and Vinod Vaikuntanathan. “Revocable Cryptography from Learning with Errors”. In: TCC. 2023 (cit. on p. 7).

[BBBV97]

Charles H. Bennett, Ethan Bernstein, Gilles Brassard, and Umesh Vazirani. “Strengths and weaknesses of quantum computing”. In: SIAM Journal on Computing 26.5 (1997), pp. 1510–1523 (cit. on pp. 7, 13, 14, 16, 18, 51).

[BCR26]

Anne Broadbent, Eric Culf, and Denis Rochette. “Optimal Untelegraphable Encryption and Implications for Uncloneable Encryption”. In: IACR Communications in Cryptology 3.2 (2026) (cit. on p. 7).

[BGMS25a]

James Bartusek, Aparna Gupte, Saachi Mutreja, and Omri Shmueli. Classical Obfuscation of Quantum Circuits via Publicly-Verifiable QFHE. arXiv:2510.08400. 2025 (cit. on pp. 4, 7, 9).

[BGMS25b]

James Bartusek, Aparna Gupte, Saachi Mutreja, and Omri Shmueli. “Classical obfuscation of quantum circuits via publicly-verifiable qfhe”. In: arXiv preprint arXiv:2510.08400 (2025) (cit. on pp. 23, 24).

67

[BGPS25]

Anne Broadbent, Alex B Grilo, Supartha Podder, and Jamie Sikora. “The Role of piracy in quantum proofs”. In: International Conference on Cryptology and Information Security in Latin America. Springer. 2025, pp. 267–295 (cit. on p. 3).

[BJLPS21]

Anne Broadbent, Stacey Jeffery, Sébastien Lord, Supartha Podder, and Aarthi Sundaram. “Secure software leasing without assumptions”. In: Theory of cryptography conference. Springer. 2021, pp. 90–120 (cit. on p. 3).

[BKL23]

Anne Broadbent, Martti Karvonen, and Sébastien Lord. “Uncloneable quantum advice”. In: arXiv preprint arXiv:2309.05155 (2023) (cit. on p. 3).

[BL20]

Anne Broadbent and Sébastien Lord. “Uncloneable Quantum Encryption via Oracles”. In: TQC. 2020 (cit. on pp. 3, 7, 15).

[BNZ25]

John Bostanci, Barak Nehoran, and Mark Zhandry. “A General Quantum Duality for Representations of Groups with Applications to Quantum Money, Lightning, and Fire”. In: STOC. 2025 (cit. on pp. 3, 6).

[BS23]

Shalev Ben-David and Or Sattath. “Quantum Tokens for Digital Signatures”. In: Quantum 7 (2023) (cit. on pp. 4, 7).

[ÇG24]

Alper Çakan and Vipul Goyal. Unclonable Cryptography with Unbounded Collusions and Impossibility of Hyperefficient Shadow Tomography. Cryptology ePrint Archive, Paper 2023/1841. 2024 (cit. on pp. 7, 15).

[ÇGLR24]

Alper Çakan, Vipul Goyal, Chen-Da Liu-Zhang, and João Ribeiro. “Unbounded Leakage-Resilience and Leakage-Detection in a Quantum World”. In: TCC. 2024 (cit. on p. 7).

[ÇGS26]

Alper Çakan, Vipul Goyal, and Omri Shmueli. Public-Key Quantum Fire and KeyFire From Classical Oracles. arXiv:2504.16407v2 (version of 14 March 2026); CRYPTO 2026. 2026 (cit. on pp. 3, 5–7, 10–12, 19, 21, 22, 24, 26, 28, 29, 38).

[CKNY25]

Jeffrey Champion, Fuyuki Kitagawa, Ryo Nishimaki, and Takashi Yamakawa. “Untelegraphable Encryption and its Applications”. In: TCC. 2025, pp. 3–35 (cit. on p. 7).

[CKP25]

Rohit Chatterjee, Srijita Kundu, and Supartha Podder. “Uncloneable quantum states are necessary as proofs and advice”. In: Proceedings of the 57th Annual ACM Symposium on Theory of Computing. 2025, pp. 1817–1827 (cit. on p. 3).

[CLLZ21]

Andrea Coladangelo, Jiahui Liu, Qipeng Liu, and Mark Zhandry. “Hidden Cosets and Applications to Unclonable Cryptography”. In: CRYPTO. 2021 (cit. on p. 3).

[CLPY25]

Rohit Chatterjee, Xiao Liang, Omkant Pandey, and Takashi Yamakawa. “The Round Complexity of Black-Box Post-Quantum Secure Computation”. In: CRYPTO. 2025 (cit. on pp. 7, 15, 49).

[CLX26]

Andrea Coladangelo, Qipeng Liu, and Ziyi Xie. Unclonable encryption from BB84 states: a simultaneous Goldreich-Levin reduction. Cryptology ePrint Archive, Paper 2026/1742. 2026 (cit. on pp. 7, 15).

[CMP24]

Andrea Coladangelo, Christian Majenz, and Alexander Poremba. “Quantum copyprotection of compute-and-compare programs in the quantum random oracle model”. In: Quantum 8 (2024), p. 1330 (cit. on pp. 7, 15, 49, 50).

68

[CMSZ21]

Alessandro Chiesa, Fermi Ma, Nicholas Spooner, and Mark Zhandry. “Post-Quantum Succinct Arguments: Breaking the Quantum Rewinding Barrier”. In: 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021, Denver, CO, USA, February 7-10, 2022. IEEE, 2021, pp. 49–58. DOI: 10.1109/FOCS52979.2021.00014. arXiv: 2103.08140. URL: https://doi.org (cit. on pp. 7, 14, 54).

[CNS26]

Ofer Casper, Barak Nehoran, and Or Sattath. Publicly Certifiable Min-Entropy Without Quantum Communication. Cryptology ePrint Archive, Paper 2026/356. 2026 (cit. on pp. 3, 4, 6, 7, 9, 10, 30, 31).

[Die82]

Dennis Dieks. “Communication by EPR devices”. In: Physics Letters A 92.6 (1982), pp. 271–272 (cit. on p. 3).

[HLM17]

Aram W. Harrow, Cedric Yen-Yu Lin, and Ashley Montanaro. “Sequential Measurements, Disturbance and Property Testing”. In: Proceedings of SODA 2017. 2017, pp. 1598–1611. DOI: 10.1137/1.9781611974782.105. URL: https://arxiv.org/ abs/1607.03236 (cit. on pp. 50, 52).

[HSVZ26]

Andrew Huang, Omri Shmueli, Vinod Vaikuntanathan, and Mark Zhandry. Uncloneable Cryptography in Linear Quantum Memory. Cryptology ePrint Archive, Paper 2026/1210. Full version of the CRYPTO 2026 paper. 2026 (cit. on pp. 7, 8, 22, 23).

[HV25]

Andrew Huang and Vinod Vaikuntanathan. A Simple and Efficient One-Shot Signature Scheme. Cryptology ePrint Archive, Paper 2025/1906. 2025 (cit. on pp. 7, 8, 22).

[KN22]

Fuyuki Kitagawa and Ryo Nishimaki. “Functional Encryption with Secure Key Leasing”. In: ASIACRYPT. 2022 (cit. on p. 7).

[KSSSS20]

Veronika Kuchta, Amin Sakzad, Damien Stehlé, Ron Steinfeld, and Shi-Feng Sun. “Measure-Rewind-Measure: Tighter Quantum Random Oracle Model Proofs for One-Way to Hiding and CCA Security”. In: EUROCRYPT. 2020 (cit. on p. 14).

[LLQZ22]

Jiahui Liu, Qipeng Liu, Luowen Qian, and Mark Zhandry. “Collusion Resistant Copy-Protection for Watermarkable Functionalities”. In: TCC. 2022 (cit. on pp. 7, 15).

[LMS22]

Alex Lombardi, Fermi Ma, and Nicholas Spooner. “Post-Quantum Zero Knowledge, Revisited (or: How to Do Quantum Rewinding Undetectably)”. In: FOCS. 2022 (cit. on pp. 7, 14).

[MST21]

Christian Majenz, Christian Schaffner, and Mehrdad Tahmasbi. Limitations on Uncloneable Encryption and Simultaneous One-Way-to-Hiding. arXiv:2103.14510, Cryptology ePrint Archive 2021/408. 2021 (cit. on pp. 7, 15).

[MW05]

Chris Marriott and John Watrous. “Quantum Arthur–Merlin games”. In: Computational Complexity 14.2 (2005), pp. 122–152 (cit. on pp. 7, 14, 54).

[NC00]

Michael A. Nielsen and Isaac L. Chuang. Quantum Computation and Quantum Information. Cambridge University Press, 2000 (cit. on pp. 16, 18).

[NWZ09]

Daniel Nagaj, Pawel Wocjan, and Yong Zhang. “Fast Amplification of QMA”. In: Quantum Information & Computation 9.11–12 (2009), pp. 1053–1068. URL: https:// arxiv.org/abs/0904.1549 (cit. on p. 54).

[NZ24]

Barak Nehoran and Mark Zhandry. “A Computational Separation Between Quantum No-cloning and No-telegraphing”. In: ITCS. 2024 (cit. on pp. 3, 6).

69

[SZ25]

Omri Shmueli and Mark Zhandry. “On One-Shot Signatures, Quantum vs. Classical Binding, and Obfuscating Permutations”. In: CRYPTO. 2025, pp. 350–383 (cit. on pp. 3–9, 11, 19, 20, 22, 23).

[TFKW13]

Marco Tomamichel, Serge Fehr, J˛edrzej Kaniewski, and Stephanie Wehner. “A monogamyof-entanglement game with applications to device-independent quantum cryptography”. In: New Journal of Physics 15 (2013) (cit. on p. 7).

[Unr15]

Dominique Unruh. “Revocable Quantum Timed-Release Encryption”. In: Journal of the ACM 62.6 (2015) (cit. on pp. 7, 13, 14).

[Wer01]

Reinhard F. Werner. “All teleportation and dense coding schemes”. In: Journal of Physics A: Mathematical and General 34.35 (2001), pp. 7081–7094 (cit. on p. 3).

[Wie83]

Stephen Wiesner. “Conjugate coding”. In: SIGACT News 15.1 (1983), pp. 78–88 (cit. on p. 3).

[WZ82]

William K. Wootters and Wojciech H. Zurek. “A single quantum cannot be cloned”. In: Nature 299 (1982), pp. 802–803 (cit. on p. 3).

[Zha19]

Mark Zhandry. “Quantum Lightning Never Strikes the Same State Twice”. In: EUROCRYPT. 2019 (cit. on p. 3).

[Zha20]

Mark Zhandry. “Schrödinger’s Pirate: How to Trace a Quantum Decoder”. In: TCC. 2020 (cit. on pp. 7, 14, 15).

A

Deferred details from Construction 4.22

A.1

Coherent Tag Generation

We start with the following tool. For, the signing algorithm of Construction 4.7, the coherent O and signing circuit of Remark 4.12 is available using the public collection O . We denote it by Uy,b use the signing algorithm with security parameter µ. Coherent tag circuit. Recall that the flame register is F = YU. For each b ∈ {0, 1}, let Eb be signing O acts on UE Σ . workspace and let Σb hold the signature. The coherent signing circuit Uy,b b b To apply this circuit without measuring the verification key in Y, define bO = U b

∑

O |y⟩⟨y|Y ⊗ Uy,b .

y∈{0,1}r

b O acts on YUEb Σb : Y is the control register, and UEb Σb are the registers on which the Thus U b selected signing circuit acts. Let Z hold the query, and let R0 , R1 hold the two oracle responses. Initialize Eb , Σb , Rb to zero for each b. The oracle query unitary UOb acts on YΣb ZRb : it uses (Y, Σb , Z ) as its input registers and writes the response into Rb , leaving Y, Σb , Z unchanged. For each bit b, perform the following operations: b O to YUEb Σb to compute the signature in Σb . (i) Apply U b (ii) Apply UOb to YΣb ZRb to obtain the oracle response in Rb . b O )† to YUEb Σb , leaving Z and Rb untouched. (iii) Apply (U b

70

Each operation acts as the identity on registers not listed above. Writing TbO for this sequence, define b O )† UO U b O , b ∈ {0, 1}, TbO = (U b b b (95) O O O Fire.Tag = T1 T0 . Thus T0O is applied first, followed by T1O . Both use the same registers Y, U, Z, with separate auxiliary registers Eb , Σb , Rb . The tag is held in (Y, R0 , R1 ). All auxiliary registers are retained so that (Fire.TagO )† can later be applied to the same registers.

A.2

Implementation Details of Cloning a flame

Encode each oracle call in a query register Z using enc from (21). Let C denote its answer register. For each call, introduce fresh zero auxiliary registers E0 , Σ0 , R0 , E1 , Σ1 , R1 and execute: (i) Apply Fire.TagO to FZE0 Σ0 R0 E1 Σ1 R1 . The resulting tag occupies (Y, R0 , R1 ). (ii) Apply the public query unitary UO2 . Its input registers are ( Z, Y, R0 , R1 ), and its answer register is C. For a valid tag, O2 returns the value of the encoded forward or inverse call. (iii) Apply (Fire.TagO )† to the same registers as in Step (i), leaving C untouched. Thus the public circuit replacing each G query is e GO = (Fire.TagO )† UO Fire.TagO . U 2

B

Deferred details from Construction 7.4

B.1

Coherent execution of an affine query

(96)

Coherent preparation of an affine query. Fix a serial s = (ℓ, a), a published torch key t ∈ Tpub , a component c ∈ [ L], and e ∈ {0, 1}. We describe how the anchor A, torch T, and CGS flame part K are used to request a value of affineac ,e from Γ in a coherent way. O Let X hold the affine input u and let C be the answer register. The preparation circuit Sc,e performs the following operations, with fresh auxiliary registers initialized to zero. (i) Form the request. Coherently compute q = (s, t, c, e, u),

zq = enc(forward, code(q))

into registers Q, Z, respectively, leaving X unchanged. The encoding is the one defined in (44). (ii) Prepare the CGS tag. Write K = YU and apply Fire.TagO from (95) to K with request register Z. This uses D , O0 , O1 from the CGS fire source OK . If R0 , R1 denote the response registers of that circuit, the tag occupies (Y, R0 , R1 ). Retain all its auxiliary registers for the inverse operation.

71

(iii) Prepare the two signatures. Using the messages in (43), apply O

A,ℓ Ua,M (s,t) A

to A,

OT Ut,M (s,t) T

to T,

with their zero signing workspace, and store the signatures in Σ A , Σ T . These are the coherent long-message signing circuits of (15); each uses its source’s digest oracle and component D interfaces. Retain the signing workspace as in Remark 4.12. O preserves X and acts trivially on C. The signatures and tag are kept coherent The circuit Sc,e throughout.

Querying and reversing the preparation.

O , query Γ with inputs After applying Sc,e

( Q, (Y, R0 , R1 ), Σ A , ΣT ) and answer register C. The oracle checks the signatures and tag as in (45) and returns the reO )† to the preparation registers, leaving quested affine value when the checks pass. Then apply (Sc,e C untouched. This defines O † O (97) RO c,e = ( Sc,e ) UΓ Sc,e . All workspace is retained until the inverse is applied. No signature, tag, or answer is measured. The approximation to an ideal affine query on honest resources is proved in Lemma 7.6.

B.2

Proof of Lemma 7.6

Proof. Here U = Uaffineac ,e is the ideal affine-query unitary. For fixed a, c, e, write f (u) = affineac ,e (u). Then
U |u⟩ X |z⟩C ⊗ |η ⟩ = |u⟩ X |z ⊕ f (u)⟩C ⊗ |η ⟩ . It writes the affine value into C and leaves every other register unchanged. O from (97). Let P project onto correctly encoded reAlso, recall the preparation circuit S = Sc,e quests for the input in X that pass (45). The preparation encodes these requests correctly, so the signing and tag bounds (50) and (51) give ∥( I − P)S |ψ⟩∥2 ≤ d. On this subspace, Γ returns the ideal affine value: (UΓ − U ) P = 0. Also, S, U commute since S preserves X and does not act on C. Consequently,

† RO c,e − Uaffineac ,e | ψ ⟩ = ( S UΓ S − U ) | ψ ⟩ = ∥(UΓ − U )( I − P ) S | ψ ⟩∥ √ ≤ 2 ∥( I − P)S |ψ⟩∥ ≤ 2 d. The expectation bound follows from (50) and (52).

72

Related documents

• Quantum Fire with Delegated Cloning#1188304
• Entanglement Swapping Enables the Practical Security of Quantum Cryptography.#232578
• Authentication in Quantum Networks#339500
• Authentication in Quantum Networks#321730
• Time-Frequency Continuous-Variable Quantum Teleportation with Single Photons#1327788