A quantum algorithm for one-shot signatures

Unknown

Conceptio › Archive › arXiv CS

arXiv CSopen access

A quantum algorithm for one-shot signatures

Unknown · 2026 · arxiv_cs

arXiv CS · Papers · License: Open Access · 2026

Open Source ↗Direct PDF ↓

cryptography, security, privacy, cybersecurity

A quantum algorithm for one-shot signatures Gopikrishnan Muraleedharan,1, ∗ Minh Thuy Truc Pham,1 Vir Pathak,1 Thomas Gardner,1 Chuanqi Zhang,1 QPerfect,2 and Gavin K. Brennen1 1

arXiv:2606.23612v1 [quant-ph] 22 Jun 2026

BTQ Technologies, 16-104 555 Burrard Street, Vancouver BC, V7X 1M8 Canada 2 QPerfect, 23 Rue du Loess, 67200 Strasbourg, France We provide a pre-obfuscation circuit-level implementation of an efficient one shot signature scheme, which has known applications to delegated signatures, secured token transfer, and publicly verifiable randomness. The algorithm consists of two stages: a key generation stage where a classical public key/quantum secret key pair is produced, and a signing stage where the quantum secret key is processed with a message string to produce a classical signature. There is no algorithmic error in the construction and the signed message can be efficiently checked by a classical verifier. Our scheme works by preparing a superposition over elements of a random affine coset determined by the output of a puncturable pseudorandom function, together with a circuit that tests coset membership. The logical qubit number scales like Θ(κ log(r) + n + l) and the gate complexity scales like Θ(n3 + nl), where r is the public key size, n + l is the signature size, l is the message size, and κ = Ω(n) is the cryptographic security parameter. We provide explicit qubit and gate counts for varying n and identify the circuit components where obfuscation would be required for security against classical and quantum polynomial time attacks.

I. INTRODUCTION

The study of quantum algorithms is frequently framed within the context of computational complexity, where seminal protocols, such as Grover’s algorithm (Gro96) and Shor’s algorithm for integer factorization and breaking Elliptic Curve Cryptography (ECC) (Sho94; Sho99), demonstrate the capacity to efficiently solve classically intractable problems. Consequently, the impact of quantum computing on modern cryptography is mainly viewed as an adversarial threat to existing public-key infrastructure, rather than a resource for building fundamentally new security models. This perceived vulnerability has catalyzed the ongoing global transition into post-quantum cryptography (CCJ+ 16). However, this perspective overlooks the constructive potential of quantum mechanics. Beyond merely undermining classical encryption, quantum computing provides a robust foundation for novel cryptographic design, enabling functionalities and security guarantees that are simply impossible within a purely classical framework. This constructive paradigm is best exemplified by “local quantum cryptography” (also referred to as hybrid quantum cryptography), an emerging research field that restricts operations entirely to local quantum computation and classical communication. Crucially, this framework eliminates the need for a quantum internet. Network communication between parties remains classical, functioning identically to traditional cryptographic protocols. The innovation instead lies at the endpoints by replacing classical hardware at specific local nodes with quantum technologies. By generating and storing cryptographic assets as quantum states locally, the system drastically enhances security capabilities without requiring any alterations to the existing classical communication infrastructure. Although the work initially attracted less attention than quantum communication based cryptography, the notion has since become increasingly influential due to its useful applications and its foundational role in local quantum cryptography. Specifically, this regime operates under the premise that while communication channels between parties remain entirely classical, the participating entities leverage local quantum states to secure and process data. By exploiting the physical constraints of quantum information, most notably the no-cloning theorem (WZ82) and measurementinduced state collapse, cryptographic capabilities can be physically bound to a quantum system. Slightly shifting the focus, one of the most fundamental building blocks in cryptography is the digital signature, whereby a message is signed using a secret key verifiable by anyone holding that same secret key in the symmetric setting, or by anyone holding the corresponding public key in the asymmetric setting. Many variants of digital signatures have since been

∗ Author to whom any correspondence should be addressed: [email protected]

2 proposed, each extending the base primitive with additional properties to meet the demands of specific applications. In 2020, Amos, Georgiou, Kiayias, and Zhandry introduced the concept of One-Shot Signatures (OSS) (AGKZ20), a primitive that can be seen as one such variant, further extending the classical notion of digital signatures into the quantum realm, which can be marked as the foundational work for local quantum cryptography. In the context of one-shot signatures, a user’s signing key is encoded directly into a fragile quantum state. The act of executing the signature algorithm necessitates a measurement that inherently and irreversibly consumes the key. This physical enforcement, together with a classical scheme that hides the program that produces the quantum state, guarantees unclonability and ensures strict single-use policies entirely at the local level, eliminating the threat of key duplication and providing a fundamentally new primitive for secure digital delegation. Nevertheless, the original paper (AGKZ20) left two major gaps: it did not present an explicit construction of the so-called equivocal hash function, a key building block of the scheme, and it contained a critical flaw in its security proof. The year 2025 marked a turning point, with several breakthroughs addressing these problems. The works by Shmueli and Zhandry (SZ25a) and (SZ25b) repaired the proof and provided the first concrete construction of an OSS. Later that year, Huang and Vaikuntanathan (HV25) strengthened that construction by extending the scheme’s functionality from signing a single bit to signing longer messages. Additional follow-up research further expanded the landscape, revealing new applications of the one-shot framework across multiple cryptographic settings. Those aforementioned works, however, are at the level of a formal protocol without providing an explicit quantum algorithm or circuit representation and resource analysis. In this work, we give complete quantum circuit level implementations for the algorithmic components of One-Shot Signatures. The quantum key generation involves sampling a uniform superposition over states from a random affine subspace. The key component is a pseudorandom function which we implement using a pseudorandom generator called within a Goldreich-Goldwasser-Micali (GGM) construction (GGM86) together with an affine subspace sampler using a novel quantum subroutine based on the Bruhat decomposition. We also introduce a simpler algorithm for signing l-bit messages using a global measurement and a single translation using one multi-control phase gate instead of l instances thereof (HV25). OSS can be thought of as part of a broader movement known as uncloneable cryptography, where the goal is to leverage the no-cloning theorem in order to achieve cryptographic constructions which are impossible via classical computation alone. A popular technique enabling many such constructions comes from the notion of hidden subspaces. Such schemes depend on the ability to find points in some hidden subspace given oracles. Using this technique, primitives such as public key quantum money (with classical communication) (AC12), and tokenized signatures (BDS23) became within reach. Coladangelo, Liu, Liu, and Zhandry (CLLZ22) generalize this technique to hidden cosets and show how to obtain similar constructions that are computationally secure in a plain model (as opposed to a classical oracle model) via obfuscated coset membership checking circuits instead of oracles. The construction of OSS we implement relies directly on such principles. With it, we can obtain a simple construction of quantum money using just classical communication, as in (AC12). Furthermore, OSS yields a straightforward construction of quantum lightning. Introduced by Zhandry, quantum lightning further strengthens quantum money by requiring that even the party who devised the original state cannot produce two valid copies; subsequent works have exploited the structural connection between OSS and quantum monetary systems to advance this program (Shm22; SZ25a). This connection also motivated a concrete line of work on quantum payment schemes. Coladangelo and Sattath (CS20) showed that quantum money can replace a public ledger to address blockchain scalability. Building on this, Sattath (Sat22) used OSS as the central building block for quantum prudent contracts: since double-spending is physically impossible by the one-shot property, no blockchain or mining is required, and transactions are locally verifiable with no throughput limit. A more recent development inspired by the creation of OSS is quantum fire (CGS25; CNS26; BNZ25), where quantum states are simultaneously clonable and untelegraphable. Using quantum fire, with OSS as a building block, one can obtain publicly certifiable randomness and trustless random beacons (CNS26). The security of most existing OSS constructions relies on the assumption of sub-exponentially secure Indistinguishability Obfuscation (iO). Broadly, program obfuscation can be considered as a “compiler” that scrambles a program , making it difficult to reverse engineer while preserving its original functionality. In recent years, obfuscation has become an active research topic, with the primary goal of preventing attacks by obscuring the inner workings, logic, and structure of a program. Some techniques further attempt to hide input/output dependencies. Early research established that Virtual Black Box (VBB) obfuscation, the ideal standard where an obfuscated program is as opaque as a black box, is generally impossible for all circuits (Bar12). Consequently, the field shifted toward iO, which guarantees that the obfuscations of any two functionally equivalent circuits are computationally indistinguishable. Approaches to constructing iO can be divided into two primary categories: quantum circuit obfuscation and post-quantum iO. The first category utilizes dummy gates, inverse gates, and mathematically equivalent “cloaked” gates to hide circuit logic (BJJ+ 25; PRS+ 25). This approach generally relies on structural complexity and heuristic techniques rather than

3 formal mathematical proofs of hardness; its main objective is to resist reverse engineering. However, a recent work has demonstrated attacks against this technique using ML-based algorithms (LS25). The second category, post-quantum iO (BDJ+ 24; Sor25; JJMP25; MDS25), is built primarily upon the hardness of Learning With Errors (LWE) problems or mathematical proofs of equivalence. While this direction offers solid security proofs based on hardness assumptions, it focuses mainly on demonstrating the existence of iO schemes and remains largely impractical. Although state-ofthe-art work has achieved a quasilinear blow-up compared to the size of the original circuit (MDS25), this overhead remains too large for our OSS implementation. Therefore, in this work, we focus on implementing the unobfuscated version of OSS. It is important to note that the fundamental building block of OSS is the Puncturable Pseudorandom Function (PPRF); consequently, one can naturally integrate our work with future practical iO schemes. The remainder of this paper is organized as follows. Section II establishes the theoretical background, formalizing the definition of one-shot signatures, reviewing the foundational SZ25 protocol, introducing our hybrid oracle-plain model, and discussing practical applications. In Section III, we detail our concrete algorithmic implementation, providing explicit quantum circuit constructions and workflows for key generation, multi-bit signing, and classical verification. Section IV presents a comprehensive logical resource analysis, detailing the qubit requirements and gate complexities of our proposed circuits. Finally, Section V analyzes the concrete security of our implementation, including parameter selection, potential attack vectors, and a detailed discussion on the necessary classical and quantum obfuscation layers, before concluding the paper in Section VI.

II. BACKGROUND

One can think of a One-Shot Signature (OSS) scheme as an asymmetric digital signature scheme satisfying the oneshot property. Concretely, an entity that has a quantum computer generates a pair consisting of a quantum secret key and a corresponding classical public key. Because the secret key is a quantum state intended for a single use, reusing it is physically impossible: once used to sign a message, the state collapses upon measurement and the measurement output is the classical signature; hence, the key is irreversibly destroyed in the process. This physical destruction ensures that the key cannot be reused, copied, or duplicated after signing. Crucially, this setting requires only a local quantum computer on the signer’s side; all other parties remain entirely classical, and all communication is performed over classical channels. This is precisely why several previous works have considered OSS as a foundational primitive for a hybrid approach that keeps both the classical and quantum components, or equivalently, for local quantum cryptography. This stands in sharp contrast to any purely classical approach: a classical approach to attaining the one-shot property would require some form of global consensus, such as a distributed ledger, e.g. a blockchain, or a trusted bulletin board, to enforce it externally, which significantly slows verification and introduces additional trust and scalability overheads. By contrast, when the secret key is stored as a quantum state, the one-shot property is enforced physically, making it possible to implement OSS with constant classical communication complexity, as verification requires only a direct check of the classical signature against the classical public key. With this intuition in place, a formal definition of the OSS scheme is given below. In the following we make use of the notation negl(x) to denote the class of functions that falls off faster than the inverse of any polynomial (KL07). Definition 1. A one shot signature scheme (OSS) with security parameter λ comprises the following algorithms. • crs ← Setup(1λ ). A classical probabilistic polynomial-time routine that samples a classical common reference string. The intention is that a trusted third-party runs the routine and publicizes the result. This defines a consistent operating environment for all interested parties. • (pk, |sk⟩) ← KeyGen(crs). A quantum polynomial-time algorithm that samples a key pair with classical public key, pk, and quantum secret key, |sk⟩. • σ ← Sign(crs, |sk⟩ , m). A quantum polynomial-time algorithm that samples a signature, σ, for any message m ∈ Mλ . • Verify(crs, pk, m, σ) ∈ {0, 1}. A classical deterministic polynomial-time algorithm that verifies the message– signature pair, (m, σ). The algorithms satisfy the following Correctness and Security properties for a negligible function negl(·):

4 • Correctness:  crs ← Setup(1λ ) Pr Verify(crs, pk, m, σ) = 1 : (pk, |sk⟩ ← KeyGen(crs)  = 1 − negl(λ). σm ← Sign(crs, |sk⟩ , m) 

• Security: For any quantum polynomial time adversary A and for all λ ∈ N   ∧(m0 , σ0 ) ̸= (m1 , σ1 ) λ crs ← Setup(1 )  ≤ negl(λ). Pr  ∧Verify(crs, pk, m0 , σ0 ) = 1 : (pk, m0 , m1 , σ0 , σ1 ) ← A(crs) ∧Verify(crs, pk, m1 , σ1 ) = 1

(2.1)

(2.2)

Since this work focuses on the unobfuscated OSS construction, we concentrate attention on the three core algorithms, (KeyGen, Sign, Verify). A. High-level structure of the SZ25 OSS protocol 1. Setup

(SZ25a) builds the scheme above from three circuits, P , P −1 , and D, derived from the common reference string returned by Setup. The circuits require access to two keyed pseudorandom routines, and so are subject to obfuscation before being broadcast. The first is a permutable pseudorandom permutation (PPRP) Π : Zn2 → Zn2 , which for clarity we write as Π(x) = (y, z), with y ∈ Zr2 and z ∈ Zn−r . The second is a puncturable pseudorandom function (PPRF), F : Zr2 → GraffZ2 (n − 2 F

r, n); y 7→ (Ay , by ), that produces an affine Grassmannian over Z2 , where we denote the affine Grassmannian by the matrix–vector pair that maps Zn−r into the Zn2 subspace. The pseudorandom function key of size κ is hardwired into 2 the obfuscated circuits. If any information about the PPRF key were revealed, information about the hidden subspace associated to the public verification key is leaked which could lead to signature forgeries. With the aforementioned setup, we can build the P circuit as follows. Say that Π(x) = (y, z), and F (y) = (Ay , by ), then P (x) = (y, Ay z + by ) =: (yx , ux ). We will refer to these tuple elements as the hash and the coset point. The circuit P −1 : Zr2 × Zn2 → Zn2 ∪ {⊥} is in essence the inverse of P extended onto Zn2 . It returns ⊥ if the input is an invalid hash–coset pair, and the corresponding x otherwise. The last circuit is essential to the signing procedure. It takes the form D : Zr2 × Zn2 → {0, 1} and tests, for a given y and u, whether ATy u = 0. 2. Key generation

A high level view of the key generation is a program like the following. 1 KeyGen : −−−−→ |0n+r+k ⟩ X H ⊗n −−−→ |X|−1/2 |x, 0r+k ⟩ Reset

x∈X P

−1/2

− → |X|

|x, yx , ux ⟩

x∈X P −1

−−−→ |X|−1/2

|0, yx , ux ⟩

x∈X Measure

−−−−−→ |X ′ |−1/2 |0, y⟩

|ux ⟩

x∈X ′

Here, H is the Hadamard gate, and the final measurement is done on the middle r qubit register, which holds the public key. The final sum is over the entire secret coset that F associates with y. The signing procedure does not work unless the x register is disentangled. The public key is the value that was measured, and the secret key is the partially measured state. f G 1 We use the notation − → to denote the application of a quantum gate, G; − → to denote the application of the classical function f , Circuit

implemented as a quantum query oracle, Uf |x, y⟩ = |x, y + f (x)⟩; and −−−−−→ to denote the application of quantum circuit Circuit.

5 3. Signing

A valid signature for public key, y, is any point in the secret coset, Cy := by + Im(Ay ) where Im(Ay ) = {Ay z : (n−r) z ∈ Z2 }. Given such a point, u, we interpret it as a signature for bit b if u1 = b. The algorithm Sign(y, |sky ⟩ , b) generates this value by performing an adapted Amplitude Amplification on the secret key state, and measuring the secret key state (AGKZ20). 4. Verification

The verification algorithm is a classical, deterministic polynomial-time procedure that, given a common reference string crs, a public key pk = y, a message bit m, and a signature σ, ensures that the generated signature is valid. Based on the protocol’s construction, the verifier utilizes the inverse function P −1 , which is accessible either as a classical oracle or instantiated via indistinguishability obfuscation within the crs. The algorithm parses the public key as y and the signature as σ, outputting 1 (accept) if and only if both of the following conditions are satisfied: 1. Validity of Pre-image: The evaluation of the inverse function does not output the rejection symbol, ensuring that P −1 (y, σ) ̸= ⊥. 2. Message Binding: The first bit of the signature σ matches the signed message bit m. B. A streamlined construction for OSS

The construction of Shmueli and Zhandry (SZ25a) establishes OSS in the plain model by introducing a PPRP. At a high level, the plain model implementation uses a program P built from a PPRP Π and a PPRF F . The PPRP serves a structural role: it ensures that the values populating the output register during key generation were produced by a controlled, obfuscatable permutation, rather than by an unprotected uniform sampling procedure. The PPRP itself is constructed on top of the underlying PPRF via a binary tally tree, a hierarchical structure that propagates pseudorandomness through successive levels to build a full-domain permutation. The PPRFs play dual roles in this construction: There is a PPRF F used directly as the pseudorandom arithmetic component, and additionally, another PPRF F ′ used as the underlying building block from which the PPRP Π is derived. Thus, the full construction depends on PPRF instantiation that is leveraged twice. While this construction is sound, traversing the tally tree demands substantial circuit depth and qubit overhead, making a direct implementation resource-intensive. A key observation, however, motivates a simplification. Consider an input of length n bits, so that the full input ⊗n space is Zn2 . Since |+⟩ is an eigenstate of any permutation Π, applying Π to the uniform superposition leaves the state invariant. Concretely, whereas the original KeyGen applies Π to the uniform superposition before passing it to F and the linear arithmetic component, our modified KeyGen algorithm replaces this step entirely with H ⊗n , leaving F and all subsequent operations unchanged. As a consequence, only the one PPRF F is now used in its direct role of producing the secret-key state; Π is no longer required. The crs still contains obfuscated programs for P , P −1 and D; however, these programs are modified with respect to the original construction: the PPRP Π inside each program is omitted while the PPRF F and the linear arithmetic component remain unchanged. This modification of omitting Π does open up an attack where a second secret key could be generated after the public key y has been broadcast. An adversary who knows the public key could prepare a clone ⊗(n−r) of the secret-key state by running the key generation algorithm on the initial state of the form H ⊗(n−r) |0⟩ |y⟩, thereby breaking the one-shot guarantee. This attack can be foiled by wrapping the obfuscation around the Hadamard layer as well as the other programs, so that that choice of initial state would not reproduce the secret key. We justify in Section V that this construction is secure under a suitable choice of parameters, as the adversary’s ability to produce two valid signatures for distinct messages remains computationally bounded by the hiding of the circuit structure. C. Applications

Signature delegation is one of the most important applications that motivated the creation of OSS, in which the protocol allows a party (Alice) to delegate signing authority to another party (Bob) for a single message only. This example also illustrates the continued role of Post-quantum cryptography (PQC) schemes in protecting classical

6 Classical/Quantum

Signature Delegation

⊛

Alice PQC.Gen(1λ ) → (sk, vk) PQC.Sign(sk, y) → σ

Bob

(|sk⟩, y) ← Gen (crs) Choose a message m x ← Sign (|sk⟩, m) |sk⟩ self destruct

Alice wishes to allow Bob to sign any single message of his choice on her behalf.

(m, y, σ, x)

Alice signs y using some PQC signature scheme and sends the resulting signature back to Bob. Anyone can verify the signature that Bob signed on Alice’s behalf.

Verifier ✓

PQC.Ver(vk, y, σ) → 1/0 Ver (crs, y, m, x) → 1/0

Figure 1: Signature delegation protocol. To mitigate risks from Bob’s quantum capabilities, Alice uses a post-quantum signature scheme, generating a signing key (PQC.sk) and verification key (PQC.vk). The blue arrows indicate classical communication that are public.

parties, even within a local quantum cryptography setting. OSS is used directly in this protocol: Bob, acting as the local quantum entity, generates a quantum secret key and sends the corresponding classical public key to Alice to seek authorization. A secure PQC signature scheme is then employed, through which Alice signs Bob’s public key as a means of granting that authorization. An additional party, the verifier, is also involved, responsible for checking both the validity of Alice’s authorization to Bob and the authenticity of the signature produced by Bob. A more detailed description of the signature delegation protocol is given in Figure 1. The Verifier is only considered as a passive party who verifies correctness in earlier OSS applications, which only concentrate on the interaction between Alice and Bob. One could also think about the scenario in which the Verifier has real power: the ability to control Bob’s quantum abilities and the authority to accept judgements made by weaker entities like Alice. When Alice gives permission to share her data with a hospital or healthcare service, for instance, Bob, the hospital, is only permitted to access the data to do enquiries or analysis on it once. This stops Alice’s privacy from being tampered with. The same principle can extend naturally to domains such as finance, banking, and government services. The signature delegation protocol can be naturally extended to a delegation chain. In this chain, signing authority passes sequentially through multiple parties, as shown in Figure 2. Alice remains the root classical authorizer, using a PQC signature scheme to delegate authority to the first quantum party. Each subsequent quantum party plays two roles: first, by using the OSS protocol to generate a key pair and sign their message; second, by issuing a PQC authorization to the next party in the chain. The final party uses OSS solely to produce the terminal signature. The aggregate signature consists of the complete sequence of OSS signatures and PQC authorizations from all parties, which the verifier checks end-to-end. Notably, the local quantum structure is preserved: Alice and the verifier remain entirely classical. All inter-party communication occurs over classical channels. This construction has natural applications in blockchain technologies, where authorization chains are essential. The one-shot property of OSS provides a strong security guarantee in this setting. No intermediate party can exceed their designated signing authority—each step is strictly single-use. The connection between OSS and tokenized signature schemes (BDS23) arises naturally when one observes that the OSS quantum secret key already satisfies the core requirement of a signing token: it can be used to produce exactly one valid, publicly verifiable signature before being irreversibly consumed. In a tokenized signature scheme, a signing authority holds a classical master secret key and uses it to mint such tokens on demand. OSS strengthens this setting by removing the signing authority entirely: the quantum state itself serves as the token, generated directly by the

Alice

Bob

Charlie

Dana

authorize authorize authorize Figure 2: Signature delegation chain. The signature can easily be delegated multiple times, with Bob ⇒ Charlie ⇒ · · · ⇒ Dana and the overall signature is the entire signature chain from Alice to the final signer.

signer with no classical master key and no trusted setup beyond a common reference string, and crucially, not even the key generator can produce two valid signatures for the same public key. A natural application of OSS is quantum money (Wie83). The structural resemblance is immediate: the quantum signing key in an OSS scheme is publicly verifiable, unclonable, and consumed upon use — precisely the properties demanded of a quantum banknote. This places OSS squarely within the quantum money landscape (Shm22; SZ25a), where the unforgeability of the signing key plays the role of the banknote’s unclonability guarantee, and the classical verification algorithm doubles as the merchant’s authenticity check, requiring no secret verification infrastructure. The connection deepens when one considers the stronger notion of quantum lightning (Zha21), where even the mint cannot produce two valid notes from the same serial number. An OSS scheme with a suitable structure, in particular, where the key generation procedure itself cannot be rewound or re-run to yield a second valid key, would satisfy an analogous guarantee. The delegation chain described above then allows a compelling monetary interpretation. Each link in the chain corresponds to a transfer of spending authority: the current keyholder, upon signing, irrevocably expends their quantum key and issues a classical post-quantum authorization designating the next recipient. The result is a chain of transfers that is locally and publicly verifiable at each step, requires no shared ledger or consensus mechanism, and is physically protected against double-spending by the one-shot property of the underlying OSS scheme. This mirrors the vision of quantum payment systems in which the unclonability of quantum states replaces the role of a blockchain, and suggests that the delegation construction may be of independent interest as a lightweight payment primitive. OSS is a key component of quantum fire (CGS25; CNS26; BNZ25). A quantum fire state is one which is simultaneously clonable and untelegraphable. That is, given a quantum fire state, there is a procedure to “clone” it and obtain another state that passes a public verification procedure with respect to a public serial number. However, an adversary cannot write down a classical string of polynomial length allowing another person to efficiently prepare a state passing verification. As an abstract object, quantum fire has been shown to be useful in theoretical contexts, such as a plausible method in obtaining oracle separations (BNZ25). Concretely, Casper, Nehoran, and Sattath (CNS26) constructed quantum fire in the plain model (i.e. no classical oracles) and showed how to use it to obtain publicly certifiable min-entropy. This allows for obtaining trustless random beacons, a property desired in decentralized protocols. We briefly sketch where OSS is fundamental in the quantum fire construction of (CNS26). A fire state is simply a OSS signing key |sk⟩. The serial number is set to be the corresponding verification key pk. We cannot directly clone |sk⟩, since that would violate OSS security. Instead, we ask the “cloner” to sample two public key-secret key pairs (|sk0 ⟩ , pk0 ), (|sk1 ⟩ pk1 ) and subsequently obtain a signature σ by signing pk0 ||pk1 using |sk⟩. The cloner outputs ((pk0 , pk1 , σ), pk0 , |sk0 ⟩) and ((pk0 , pk1 , σ), pk1 , |sk1 ⟩). Note that we can continue to clone in the same manner: generate a pair of public key/quantum secret key pairs and subsequently sign the public keys using one of the quantum secret keys from the previous clone operation. The sequence of clones creates a path in a binary tree structure. A child node has a signature of a pair of public keys which verifies with respect to the verification key stored in the parent node. To verify, we check if the path is consistent with respect to this relationship, and if all the signatures in this path are valid. If we only allow O(log(λ)) clones, (CNS26) shows this scheme is untelegraphable. The authors subsequently note that to generate any serial number useful for verification, it must possess at least some threshold amount of min-entropy. Therefore, such a serial number can serve as a min entropy source, and can be publicly verified by generating a fire state and running the verification algorithm on it. No trusted party is required, since (CNS26) shows that min entropy property must hold for any serial number ensuring correctness.

8 III. THE ALGORITHM

In this section, we discuss in detail our implementation of the OSS protocol providing explicit constructions of different parts of the algorithm. The Figure 3 shows abstract circuit diagrams for our programs. We start with an explanation for the circuit parameters, and follow up with detailed descriptions of each subcircuit. KeyGen Contained in CRS Inputs public key r secret key length n′ = n + l input key for PPRF klin message length l cryptographic security parameter κ = |klin| workspace w message m

|0⟩r

H ⊗r

|0⟩l

H ⊗l

|0⟩n−r |0⟩r

H ⊗n−r

|0⟩w

y = pk

|sky ⟩ Graff GGM † Lookup (klin)

GGM Lookup(klin)

|0⟩w

Obfuscated Sign |⃗y ⟩

|⃗y ⟩

|sky ⟩

H ⊗n−r

H ⊗r

GGM Lookup(klin)

|0⟩w |0⟩l

|0⟩

GGM † Lookup (klin)

Dp→m

⊗j X mj

|0⟩w

σ = m||τ

|⃗p + m⟩ ⃗ m H ⊗l

H ⊗l Obfuscated

Verify

Verification Inputs y, m, σ = m′||τ ′

GGM Tree Traversal (klin) (Classical Tree Search)

Leaf Key

˜ Graff z = Py−1 · ′ (n) By · (m′ + b(l) y ) + τ + by

Comparator 1 Zero-Padding Check ? zn−r...n = 0⊗r

AND

Accept / Reject

Comparator 2 Message Bit Check ? m′ = m

Obfuscated

Figure 3: Workflow diagram of the multi-bit OSS protocol. The dashed boxes represent the part of the circuits that need to be obfuscated and are distributed as classical instructions contained in CRS. Note that in Sign even though the control register |⃗ y ⟩ representing the public key is classical, it should be treated as a quantum register since those gates it controls are to be obfuscated. The bottom section outlines the corresponding classical verification protocol, which efficiently evaluates ˜ operation can be easily done signature validity using the provided CRS parameters. The binary matrix inversion inside Graff by reversing the classical sequence of gates used to perform binary multiplication by Ay .

A. Parameters

n = r + 23 · s = 2λ2 + λ,

k = n,

(3.1)

9 and choose the PPRF key length κ such that for 0 < δ < 1 κ ≥ (9 + 2λ(λ − 1) + λδ + 2 lg(2λ2 + λ))1/δ .

(3.2)

Here, n denotes the input length, r the the size of the OSS public key, and we pick length of the PPRF key so that κ = |klin |. The parameter s is the bloating factor of the dual subspace, expanding it by exactly s dimensions (SZ25a). More discussion on the possible attacks we consider, security parameters, and how they are chosen can be found in Sec. V.A B. Cryptographic primitives

A pseudorandom function (PRF) is a deterministic algorithm that takes as input a key k from a key space K, an input x from an input space X, and outputs F (k, x), which is computationally indistinguishable from the output of a random function. A Puncturable PRF (PPRF) is a PRF that has an extra feature that allows one to evaluate at all points except those in S by “puncturing” a set of points x ∈ S using a punctured key k S . The holes are controlled by additional key derivation and evaluation algorithms; technical details are in the next definition. Definition 2 (Puncturable PRFs (SW13)). A puncturable pseudorandom function (PPRF) is a tuple of efficient algorithms (F, Punc, Eval) with associated output-length function poly(κ) such that: • F : {0, 1}κ × {0, 1}∗ → {0, 1}poly(κ) is a deterministic polynomial time algorithm. • Punc(k, S) is a probabilistic polynomial algorithm that outputs a punctured key k S for a set of points S ⊆ {0, 1}∗ . • Eval(k S , x) is a deterministic polynomial time algorithm. Correctness: For any κ ∈ N, S ⊆ {0, 1}∗ , k ∈ {0, 1}κ , x ∈ / S, and k S in the support of Punc(k, S), we have that Eval(k S , x) = F(k, x). Security: A PPRF function F is (f (κ), negl(κ))-secure if for some function f : N → N and negl : N → [0, 1] if for any f (κ)-time (quantum) adversary A, the probability that A wins the following game is at most 21 + negl(κ): • A(1κ ) generates a set of points S ⊆ {0, 1}∗ . • The challenger chooses a random key k ← {0, 1}κ and computes the punctured key k S ← Punc(k, S). For each x ∈ S, it also sets yx0 := F (k, x) and samples a uniformly random string yx1 ← {0, 1}poly(κ) . Then, the challenger chooses a random bit b and gives k{S} and {(x, yxb )}x∈S to A. • A outputs a guess b′ for b and wins the game if and only if b′ = b. Even given access to the punctured key k S —which allows evaluation of the PPRF at all points except x∗ ∈ S—no efficient adversary can distinguish the outputs of the PPRF from truly random values. A classic construction for a PPRF is the GGM tree. This construction iterates a pseudorandom generator to build a tree of keys. Recall that a pseudorandom generator uses a short, random seed to produce a longer bit sequence that is computationally indistinguishable from a uniform random distribution. Definition 3 (Pseudorandom generator (PRG)). A pseudorandom generator (PRG) is a function G : {0, 1}κ → {0, 1}poly(κ) such that: • G is an efficient deterministic algorithm, • For any polynomial time algorithm A, for a random seed s sampled from {0, 1}κ and a value r uniformly sampled from {0, 1}poly(κ) , the distinguishing advantage of A between G(s) and r is negligible for a negligible function negl(κ) , i.e. Pr

s←{0,1}κ

[A(G(s)) = 1] −

r←{0,1}poly(κ)

[A(r) = 1] < negl(κ).

(3.3)

One can also say that the uniform distribution on {0, 1}poly(κ) is negl(κ)- indistinguishable from the distribution {G(s)|s ← {0, 1}κ }.

10 G(k)

G00

G000

G01

G001

G010

G10

G011

G100

G11

G101

G110

G111

Figure 4: Sample GGM tree with r = 3. The output of the PRG is G(k) = G0 ∥G1 . Evaluating the GGM PPRF on input 011 results in F(k, 011) = G011 = G1 (G01 ) = G1 (G1 (G0 (k)))

Given any block cipher that is a secure pseudorandom permutation (PRP), a secure PRG can be constructed using standard PRP-based domain-extension methods. For instance, one may encrypt an incrementing counter and concatenate the resulting blocks (CTR mode), or repeatedly encrypt the previous output block as the next input (CFB mode). The GGM construction (GGM86) builds a PPRF, F : {0, 1}κ × {0, 1}r → {0, 1}κ , from a length doubling PRG, G : {0, 1}κ → {0, 1}2κ . The output splits into two κ-bit strings, G(s) = G0 (s) ∥ G1 (s) | {z } | {z }

(3.4)

(3.5)

κ bits

Thae PRF is defined as, (k, y) 7→ (Gy−1 (· · · Gy1 (Gy0 (k)) · · · ))

The input y ∈ {0, 1}r determines a path of length r through the binary tree, with the leaves representing the PRF outputs. Algorithm 1: GGM PPRF F(·, ·) from a length-doubling PRG G(·) Input: (k, y) ∈ {0, 1}κ × {0, 1}r t ← k; for i ← 0 to r − 1 do c = yi ; t = Gc (t) end Result: t

Since the GGM construction is puncturable (Zha16), the punctured key for a PPRF allows evaluation of the PRF tree at all points except a specific input y ∗ . Let Py∗ be the path from root to y ∗ and Ny∗ be the set of all neighbouring nodes in Py∗ . The punctured key is the set of values of all the nodes in Ny∗ . These values define the roots of every subtree that doesn’t contain a point in the punctured path, and so all unpunctured points can still be evaluated with a standard GGM lookup. Figure 5 gives a simple example of the pucnturable property of the GGM construction. Notice that in our algorithm, it was not necessary for us to generate a punctured key for any subroutines. However, this property is important as it is compatible with the requirement of iO. See Sec. V.B.3 for more details.

C. Setup

Our setup is done at a higher level than (SZ25a). A trusted third party samples a klin ∈ {0, 1}κ and uses it to construct a crs that describes quantum programs: KeyGen and Sign, and a classical program Verify. These programs are obfuscated before being publicized. The necessary requirements for obfuscation are detailed in Sec. V.

11 G(k)

G00

G000

G01

G001

G010

G10

G011

G100

G11

G101

G110

G111

Figure 5: Puncturing the GGM tree at 011. The puncturing key is k011 = {G1 , G00 , G010 }. The punctured path is marked with a red dashed line, and the puncturing key’s nodes are in blue boxes.

D. KeyGen

As seen in the Workflow diagram 3, the key generation circuit factors as KeyGen = H ⊗n+l ; F ; Measure. The factor F is a puncturable PRF that relates public keys to a hidden coset space, encoded as an affine transformation (z 7→ Ay z + by ). The GGM construction (detailed above) is a flexible recipe for building PPRFs. However a GGM path traversal alone can not construct the desired F . This is for two reasons: 1. it does not provide enough length, and 2. it does not guarantee the requisite structure. Our construction solves both problems. It begins with a general quantum circuit for GGM tree path traversal. The GGM result is used to seed a stream cipher, which solves the length problem. The stream is passed to a novel circuit that decodes bit strings into instructions for a suitable affine transformation; this solves the structure problem. We call these factors GGM.Lookup and Graff, and describe their implementation in the sections that follow. 1. Implementing the GGM.Lookup

The GGM PPRF construction (GGM86) creates a binary tree of keys by iterating a length-doubling PRG, G : {0, 1}κ → {0, 1}2κ , along any path p ∈ {0, 1}∗ , in the pattern G(k) = (k0 , k1 ) G(kp ) = (kp||0 , kp||1 ) We call k the root key of the tree. The leaves define the value of the PPRF on a point x ∈ {0, 1}r , which defines a path through the tree from the root. To implement this as a quantum circuit, we reduce the GGM lookup to a reversible pebble game on a tree. Recall that reversible pebble games are an abstraction for reversible computations.(Ben89) Games are played on a directed graph with no cycles. Every node (in the graph) maintains a counter that tracks the number of pebbles sitting on top. The game starts with all counters at zero; each turn adds or removes a pebble, subject to the constraint that pebbles may only be added to or removed from nodes that have a pebble on all of their parents; the game is over once a pebble is placed on some special target node. Each pebble added to the graph corresponds to one register of space used in the computation. The reduction is seen by specifying a pebble operator. It’s always possible to pebble the root, since the root has no parents. This is implemented with a circuit, kLin, that writes klin into a register using CNOT gates. The children are NextKey pebbeled by the NextKey query oracle, |p, kp , 0κ ⟩ −−−−−−→ |p, kp , kq ⟩. This circuit uses the value at node p to select which half of the length doubling PRG to build. The NextKey circuit can run in one of two modes, determined by the blockcipher’s key and block size. In the case where the blocksize divides keysize in two, we initialize two blocks to |0κ/2 , 0κ/2−1 1⟩, and use the point on the path to control the second qubit. This gives |0κ/2−2 yi 0, 0κ/2−2 yi 1⟩, which is then enciphered. Otherwise, (eg, when using the Simon cipher with κ = 192) we must first allocate a separate workspace to build the key. Sufficient key material is then copied out of the workspace into a key register, and the workspace is uncomputed.

12 The simplest reversible path traversal circuit caches every intermediate key. It uses Θ(r) NextKey calls and Θ(rκ) logical qubits for a depth r tree. This is infeasible for current machines, which are bottlenecked by qubit cost. A realization is however possible by trading time complexity for space efficiency. To proceed, we present the key registers as a comma-separated row of numerals. Let 0 denote a reset register, say |0κ ⟩, |1⟩ denote the GGM root (klin ), and successors denote the key value along the GGM path. The gadgets above in this shorthand become O

0← →1 P

n, 0 ← → n, n + 1

P0,2

We use subscripts to precise relevant registers (eg, n, m, 0 −−→ n, m, n + 1) and omit them when obvious. The pebble operation with a fixed register also creates new single-register reversible operations, 0 ← → vi + 1 where vi denotes the value in register i. We reorder registers with a SWAP operation to simplify bookkeeping. The SWAPs can always be optimized out and do not contribute to gate counts. To minimize qubit counts, we ask the question: what is the greatest x that processes of the form 0R ← → x, 0R−1 R can reach? An adapted binary search works well. Use WO to denote the optimal process on R registers with a P

circuit O that pebbles the root. Run WOR−1 on the rightmost R − 1 registers to get 0R −→ 0, x∗R−1 , 0R−2 . Swap xR−1 into register zero, and run WPR−1 on the rightmost R − 1 registers, with the zero pebble set to use P0 . This 0 gives x2(R−1) , xR−1 , 0R−2 after swapping. The xR−1 , 0R−2 can be uncomputed by running W in reverse. That is WOR = WOR−1 ; SWAP; WPR−1 ; SWAP; WOR−1 † for R > 1 and WO1 = O. The R = 3 case shows the structure: R−1 O

W†

−−−−→ 0, 0, 0 − → 0, 0, 1 −−−−→ 0, 1, 0 − → 0, 1, 2 −−−−→ 0, 2, 1 − → 0, 2, 0 −−−−→ 2, 0, 0 −→ 2, 4, 0 −−−−→ 4, 2, 0 −−→ 4, 0, 0 Reset

SWAP

This gives a lower bound on how far we can place a single pebble: x∗R = 2x∗R−1 , and solving the recurrence yields x∗R = 2R . Iterating the process on the remaining free registers reaches a maximum depth of 2R − 1. The GGM Lookup routine in our OSS algorithm requires traversing a path to depth r + 1, where r is the length of the public key. This means at least R = ⌈lg(r + 2)⌉ registers are required to reach that depth. Moreover, since each W splits into three subproblems with half the problem size, the algorithm must make Θ(rlg(3) ) calls to NextKey. We note that this approach is in essence Bennett’s simulation technique from (Ben89) with m = 2. 2. Implementing the PRG

The GGM circuit builder works for any reversible implementation of a block cipher, |k, x⟩ −−−−→ |k, Cipherk (x)⟩. As noted above, the length-doubling PRG can be implemented by a block cipher run in a suitable streaming mode. Because logical qubits are the dominant resource bottleneck at present, we have focused our attention on lightweight block ciphers. Two that seem promising are Present (BKL+ 07) and Simon (BTCS+ 15). Since Simon presents far more block and key size configurations, we have expressed all concrete resource counts below assuming a Simon implementation with a suitable choice for κ. PRESENT (BKL+ 07) is a light weight block cipher that encrypts 64-bit data blocks with a key length of 80 or 128 bits. PRESENT follows the Substitution Permutation Network (SPN) method and has 31 rounds; each round consists of three steps: AddRoundKey, Sbox, and Permutation. An efficient implementation of PRESENT on quantum computers is introduced in (JSK+ 21). SIMON (BTCS+ 15) is a family of the lightweight block ciphers introduced by the U.S National Security Agency in 2013 that offers a wider range of block sizes, key sizes, and rounds. (AMM20) developed a reversible quantum circuit for all variants of SIMON. Their implementation produces the correct ciphertext, but does not unwind the key schedule. Our implementation unwinds the key schedule and leaves the input key intact; this is essential for an efficient GGM path traversal. Gate counts for our implementation are tabulated in Table I. Cipher

3. Uniform coset generation using Bruhat decomposition

Proceeding with the algorithmic workflow, the subsequent step involves generating the coset. As in the (SZ25a) construction, our implementation uses the PPRF F to sample a random coset Cy defined by a full-column rank matrix

13 Table I: Gate counts for the Simon block cipher |k, x⟩ −−−→ |k, Simonk (x)⟩ with key length κ and blocksize bk. Simon

64 96 128 144 192 256 κ bk 32 48 64 96 128 128 X 812 1 442 2 438 4 742 8 252 8 500 CX 4 608 7 872 13 056 14 976 25 728 44 032 CCX 512 864 1 408 2 592 4 416 4 608 n×(n−r)

Ay ∈ Z2 and a random vector by ∈ Zn2 . We construct this PPRF F by leveraging a GGM tree traversal to derive a leaf key, followed by repeated applications of a block cipher. Specifically, the leaf key is computed as ky = F(klin , y), which serves as the secret key for a block cipher operating in ciphertext feedback mode to expand the output to the desired length. The pseudorandom bit string output by F (klin , y) is subsequently used in conjunction with Bruhat decomposition to generate a matrix-vector pair (Ay , by ), which defines a random coset. F : {0, 1}κ × {0, 1}r −→ {0, 1}∗ F

(klin , y) 7−−−−−→ ky = F(klin , y) E

7−−−−−→ Eky (iv) ∥ Eky (Eky (iv)) ∥ . . .

(3.6)

where iv is the initialization vector of the block cipher. The columns of Ay span an (n − r)-dimensional linear subspace Im(Ay ) = {Ay z : z ∈ Zn−r }. A coset Cy of Im(Ay ) is obtained by adding a vector by to every element of Im(Ay ), 2 thereby shifting the entire subspace by by . In our setting, Cy serves as the affine subspace associated with y: Cy := by + Im(Ay ),

Im(Ay ) = {Ay z : z ∈ Zn−r }. 2

(3.7)

One subtle part left is that the output of the GGM PPRF F construction above is a pseudorandom bit string. Here, we describe how to form a random coset from F (klin , y) using the Bruhat decomposition. a. Sampling a random coset One can think of the coset Cy as an element of the affine Grassmannians GraffZ2 (n − r, n), the set of all (n − r)-dimensional affine subspaces of Zn2 , represented concretely by the pair (Ay , by ) where: GraffZ2 (n − r, n) := {(L, b) : L ∈ Gr(n − r, n)(Z2 ), b ∈ Zn2 }.

(3.8)

The set of all n − r-dimensional subspaces of an n-dimensional vector space over a field Z2 , denoted by Gr(n − r, n)(Z2 ), is called the Grassmannian. The affine Grassmannian GraffZ2 (n − r, n) extends this set by allowing subspaces to be shifted by by ∈ Zn2 . Hence, to sample a random coset Cy ∈ GraffZ2 (n − r, n), we first sample a random element Im(Ay ) in Gr(n − r, n)(Z2 ), and sample a random vector by . n×(n−r)

Note that any binary matrix Ay ∈ Z2

can always be written in the form I Ay = Py n−r Sy Ry

(3.9)

for some matrices Py ∈ GLn (Z2 ), Sy ∈ GLn−r (Z2 ), and Ry ∈ Z2r×n−r . Its columns span a (n − r)-dimensional subspace of the n-dimensional vector space over the field Z2 (with r < n). Consider any invertible matrix Py ∈ GLn (Z2 ) and a fixed (n−r)-dimensional subspace Im(Ay ) ⊆ Zn2 represented by the columns of a full-column-rank matrix Ay . Multiplying this matrix by Py simply produces another matrix whose columns span a new (n−r)-dimensional subspace P Im(Ay ). Moreover, every (n−r)-dimensional subspace of Zn2 can be expressed in this way: for any such subspace L′ , there exists an invertible matrix Py for which Py Im(Ay ) = L′ .

(3.10)

A convenient choice of reference subspace is the canonical one Z2n−r := span{e1 , . . . , en−r },

(3.11)

14 and any other (n − r)-dimensional subspace of Zn2 can be written as Py Z2n−r for some Py ∈ GLn (Z2 ). Hence, multiplying the canonical matrix by different invertible matrices GLn (Z2 ) generates all such subspaces. This also shows that the specific matrices R and S appearing in the decomposition 3.9 are not important for sampling a random subspace. Thus, we may set R = 0 and S = In−r , yielding the simplified form In−r Ay = Py . (3.12) 0 The problem of sampling a random linear subspace is now reduced to sampling a matrix Py ∈ GLn (Z2 ). We employ the Bruhat decomposition to uniformly sample invertible binary matrices; unlike other methods, it directly maps the generated random bits to the exact sequence of gates to be applied. This also makes it easier T to implement A−1 y or Ay . b. Bruhat Decomposition For GLn (Z2 ), let B be the subgroup of GLn (Z2 ) consisting of all upper triangular invertible matrices and Sn be the group of all permutation matrices. The Bruhat decomposition (Cur79) then takes the form G B π B. (3.13) GLn (Z2 ) = π∈Sn

Thus every matrix Py ∈ GLn (Z2 ) can be written as Py = U1 Sπ U2 ,

(3.14)

weith U1 , U2 ∈ B and Sπ a permutation matrix. Algorithm 2: Sample uniform element of Gr(n − r, n)(Z2 ) using Bruhat Decomposition Input: Integers n, k with 0 < k ≤ n. Sample U1 , U2 ∈ B by drawing each strict-upper entries i.i.d. uniform in Z2 . Sample π ∈ Sn with Mallows weight 2inv(π) : • For i = n, n − 1, . . . , 1: draw a uniform integer c ∈ {1, . . . , 2 i − 1}; set Li ← ⌊lg c⌋ so that Pr[Li = t] = 2t /(2 i − 1). • Convert the digits (Ln , . . . , L1 ) to the permutation Sπ . Set Py ← U1 Sπ U2 . Return A basis matrix Ay ← Py

In−r ∈ Z2n×n−r for linear subspace Im(Ay ). 0

It is important to note that sampling the permutation π uniformly from Sn does not yield a uniformly distributed matrix Py . Because the size of the Bruhat cell BπB over Z2 is proportional to 2inv(π) , where inv(π) is the number of inversions in π, the permutation must be sampled according to the Mallows distribution (MAL57; GO12) to account for this exponential difference in cell sizes. The sequence of digits (Ln , . . . , L1 ) in Algorithm 2 represents the Lehmer code of the permutation π. In a quantum circuit, this can be implemented using CSWAPs with the control on the qubits that encode the digits. While in theory some of the bits of the upper triangular matrix U1 needs to be set to 0 depending on the chosen permutation, in practice both the upper triangular matrices can be uniformly sampled, and in fact, the random bits generated by the PPRF can be directly used to fill in the non-zero elements of U1 and U2 . Binary multiplication by the upper triangular matrices can be implemented on the go by using Toffolis with the control on the qubits encoding the random bits. The translation by the vector by can be implemented by CNOTs. We require Ω(n(3n + 1)/2 − 1) pseudorandom bits to implement the random affine transform evaluation. A stream cipher mode using the GGM leaf key provides the required pseudorandom bits. 4. Generalization to multi-bit messages

This key generation module can easily be generalized to handle signatures of multi-bit messages (HV25; SZ25b). To support an l-bit message, the overall dimension of the secret key state is expanded from n to n + l. The algebraic structure is specifically designed so that the first l bits of the generated string will embed the message.

15 n×(n−r)

To achieve this, the original full-column rank matrix Ay ∈ Z2 (n+l)×(l+n−r) Ãy ∈ Z2 , defined as: Ãy =

Il 0 B y Ay

is augmented into a larger block matrix

(3.15)

where Il is the l × l identity matrix, and By ∈ Zn×l is a rectangular matrix filled with random bits generated 2 via the PPRF alongside the random bits required to implement Ay . Similarly, the random translation vector by is expanded from n bits to an (n + l)-bit string. We can partition this expanded vector into two distinct components: (1) (2) (1) (2) by = by || by , where by ∈ Zl2 and by ∈ Zn2 . When the augmented affine subspace is evaluated on an input vector constructed by concatenating an l-bit string ω and an (n − r)-bit string z (represented as the column vector [ω, z]T ), the transformation yields: # " (1) # " (1) # " (1) ω by Il 0 ω by ω + by Ãy + (2) = + (2) = (3.16) (2) z By Ay z by by By ω + Ay z + by (1)

This outputs an (n + l)-bit string where the first l bits cleanly encode the input ω shifted by by , and the remaining (2) n bits cryptographically mix ω and z through the matrices By and Ay , shifted by by . At the end of the KeyGen algorithm, the result is a quantum state containing a superposition of all possible public keys entangled with their corresponding secret key states. Measuring the public key register projects the secret key register into a superposition of all valid signatures associated with that particular public key. The user then holds on to this secret key state until a message needs to be signed. Once a message m is chosen, we move on to the KeySign algorithm. E. Sign

We apply a sequence of single qubit measurements followed by adaptive phase flips to target strings in the secret key, whose first l bits match the message and then measure the remaining k qubits to produce an l + n bits signature. We first describe the single-bit signing algorithm and then show how to generalize it to l-bit signing. The single bit signing algorithm can be constructed as a special case of multi-bit signing with l = 1. But here we follow the setup in (SZ25a) where the single bit message is encoded as the first bit of an n-bit signature. After the key-generation subroutine, the signer obtains the public key y together with the secret key quantum state of the form (3.17)

|y⟩ ⊗ |sky ⟩ ,

n×(n−r)

where the private state |sky ⟩ is an equal superposition over an affine coset of a full-rank binary matrix Ay ∈ Z2 : X 1 |Ay z + by ⟩ (3.18) |sky ⟩ = √ (n−r) 2 (n−r) z∈Z2

Here by ∈ Zn2 is a pseudorandom bit string which is a part of the KeyGen algorithm. Thus |sky ⟩ is the uniform superposition over the coset Cy := by + Im(Ay ),

(n−r)

Im(Ay ) = {Ay z : z ∈ Z2

(3.19)

1. Structure of the Coset Space

We show here that any coset C = b + Im(A) is either constant on its first coordinate or splits perfectly evenly into strings with first bit 0 and first bit 1. For x = Az + b ∈ C, the first bit is x1 = (Az + b)1 = A1 z + b1 ,

(3.20)

where A1 is the first row of A. Define C0 := {x ∈ C : x1 = 0},

C1 := {x ∈ C : x1 = 1}.

(3.21)

16 If the first row of A is the zero vector, then A1 z = 0 for every z, and therefore

a. Degenerate case: A1 = 0.

x1 = b1

for all x ∈ C.

(3.22)

(3.23)

Which means, C0 = C, C1 = ∅

C1 = C, C0 = ∅.

In this case, the coset is constant with respect to its first bit. (n−r)

A1 ̸= 0. Then there exists an index j such that A1,j = 1. For any z ∈ Z2 flipping the j-th bit and keeping all other coordinates fixed:

b. Generic case:

zj′ = ¬zj ,

(n−r)

, define z ′ ∈ Z2

zi′ = zi for all i ̸= j.

(3.24)

Since A1,j = 1, we compute A1 z ′ =

A1,i zi + A1,j ¬zj =

i̸=j

A1,i zi + ¬zj .

(3.25)

i̸=j

Using ¬zj = zj + 1, this becomes A1 z ′ =

A1,i zi + zj + 1 = A1 z + 1.

(3.26)

i̸=j (n−r)

Thus A1 z ′ always evaluates to the opposite value of A1 z, showing that a nonzero linear form on Z2 balanced. So this proves that every affine coset C = b + Im(A) satisfies exactly one of the following: Either x1 is constant on C, or C splits evenly into C0 and C1 .

is necessarily (3.27)

In all nondegenerate constructions (where A1 ̸= 0), the coset is perfectly balanced. 2. Single-Bit Signing

For a fixed public key y, write the corresponding coset Cy = by + Im(Ay ) ⊆ Zn2 .

(3.28)

Assume we are in the generic case where the first row of Ay is nonzero, so Cy splits evenly according to the first coordinate: Cy,0 := {x ∈ Cy : x1 = 0},

Cy,1 := {x ∈ Cy : x1 = 1},

(3.29)

with |Cy,0 | = |Cy,1 | = 2(n−r)−1 .

(3.30)

We define the two normalized “half-coset” states |sk0 ⟩ := √ |sk1 ⟩ := √

1 2(n−r)−1 1 2(n−r)−1

|0⟩ ⊗

|x⟩ ,

(3.31)

|x⟩ .

(3.32)

x|(0,x)∈Cy,0

|1⟩ ⊗

X x|(1,x)∈Cy,1

So that the full coset state can be written as |sky ⟩ = √

1 |x⟩ = √ |sk0 ⟩ + |sk1 ⟩ . 2 2(n−r) x∈Cy 1

Here, we write |sk⟩ := |sky ⟩ in what follows. Given a one-bit message m ∈ {0, 1}, the signer uses the first qubit of |sk⟩ as follows:

(3.33)

17 1. Measure the first qubit of |sk⟩ in the computational basis, obtaining an outcome c ∈ {0, 1}. The postmeasurement state collapses to |skc ⟩. 2. If c = m, the signer measures the remaining n − 1 qubits in the computational basis. The resulting classical string x ∈ Cy,m serves as the signature. 3. If c ̸= m, apply the logical X operator (XL ) to swap the half-coset states, transforming the state to |skm ⟩. Measure the remaining qubits to obtain the signature x ∈ Cy,m . In all cases, the final classical output lies in the desired half-coset Cy,m , i.e. its first bit equals the message bit m. To sign a message m that differs from our measured bit b, we need a reliable operation that swaps the half-coset states without measuring them. We construct this logical X operator using a phase oracle in the Fourier domain. The two orthonormal states |sk0 ⟩ and |sk1 ⟩ span a two-dimensional logical qubit. We define the logical X operator on this encoded qubit by a. Logical X on the Coset Qubit

XL := |sk0 ⟩⟨sk1 | + |sk1 ⟩⟨sk0 | .

(3.34)

By construction, XL |sk0 ⟩ = |sk1 ⟩ ,

XL |sk1 ⟩ = |sk0 ⟩ .

It is convenient to introduce the symmetric and antisymmetric combinations 1 1 |sk ′ ⟩ := √ |sk0 ⟩ − |sk1 ⟩ , |sk⟩ := √ |sk0 ⟩ + |sk1 ⟩ , 2 2

(3.35)

(3.36)

which form an orthonormal basis of the same logical subspace. We now compute the action of XL on these states: 1 1 XL |sk⟩ = √ XL |sk0 ⟩ + XL |sk1 ⟩ = √ |sk1 ⟩ + |sk0 ⟩ = |sk⟩ , 2 2 1 1 XL |sk ′ ⟩ = √ XL |sk0 ⟩ − XL |sk1 ⟩ = √ |sk1 ⟩ − |sk0 ⟩ = − |sk ′ ⟩ . 2 2 Thus |sk⟩ and |sk ′ ⟩ are eigenstates of XL with eigenvalues +1 and −1, respectively: XL |sk⟩ = + |sk⟩ ,

XL |sk ′ ⟩ = − |sk ′ ⟩ .

(3.37)

In this basis {|sk⟩ , |sk ⟩}, the logical XL plays the role of a Pauli-Z operator, while in the basis {|sk0 ⟩ , |sk1 ⟩} it acts as a standard Pauli-X that swaps the two half-coset states. ′

b. Logical X from Hadamards and a Phase on Im(Ay )⊥

|sk⟩ =

The two states

|sk0 ⟩ + |sk1 ⟩ √ , 2

|sk ′ ⟩ =

|sk0 ⟩ − |sk1 ⟩ √ 2

(3.38)

form an orthonormal basis for the two-dimensional coset subspace associated with Cy . Their structure becomes especially transparent after applying a global Hadamard transform. Let us look at how a global Hadamard gate will act on these states. For any matrix Ay of full column rank, X 1 H ⊗n |sk⟩ = √ H ⊗n |Ay z + by ⟩ (3.39) n−r 2 z∈{0,1}n−r X X 1 1 √ =√ (−1)ω.(Ay z+by ) |ω⟩ (3.40) n n−r 2 2 ω∈{0,1}n z∈{0,1}n−r   X X T 1 1 √ (3.41) =√ (−1)ω.by  (−1)(Ay ω).z  |ω⟩ 2n−r 2n ω∈{0,1}n z∈{0,1}n−r X 1 =√ (−1)ω·by |ω⟩ , r 2 ω∈Im(A )⊥ y

(3.42)

18 where Im(Ay )⊥ := {ω ∈ Zn2 : ATy ω = 0} is the orthogonal complement of the column space of Ay . Thus H ⊗n |sk⟩ has support exactly on Im(Ay )⊥ . We now analyse the Hadamard action on the other state, 1 |sk ′ ⟩ := √ (|sk0 ⟩ − |sk1 ⟩) . 2

(3.43)

(3.44)

Note that |sk ′ ⟩ is a uniform superposition over the full coset Cy = by + Im(Ay ), but with a relative phase of −1 applied to elements where the first bit is 1. Let e1 = (1, 0, . . . , 0) be the unit vector bit string corresponding to the first coordinate. For any vector x = Ay z + by ∈ Cy , its first bit is exactly the dot product e1 · (Ay z + by ). Thus, we can write |sk ′ ⟩ algebraically as: X 1 (−1)e1 ·(Ay z+by ) |Ay z + by ⟩ . (3.45) |sk ′ ⟩ = √ 2n−r z∈{0,1}n−r Applying the global Hadamard transform H ⊗n gives: X 1 H ⊗n |sk ′ ⟩ = √ (−1)e1 ·(Ay z+by ) H ⊗n |Ay z + by ⟩ 2n−r z∈{0,1}n−r X X 1 1 √ =√ (−1)e1 ·(Ay z+by ) (−1)ω·(Ay z+by ) |ω⟩ . 2n−r 2n z∈{0,1}n−r ω∈{0,1}n Since we are working on Z2 , we can combine the phases: X X 1 1 √ H ⊗n |sk ′ ⟩ = √ (−1)(ω+e1 )·(Ay z+by ) |ω⟩ 2n−r 2n ω∈{0,1}n z∈{0,1}n−r   X X T 1 1 √ (−1)(Ay (ω+e1 ))·z  |ω⟩ . (−1)(ω+e1 )·by  =√ 2n−r 2n ω∈{0,1}n n−r z∈{0,1}

(3.46) (3.47)

(3.48)

(3.49)

The inner sum over z evaluates to 2n−r if ATy (ω + e1 ) = 0, and 0 otherwise. This condition is equivalent to requiring that ω + e1 ∈ Im(Ay )⊥ . Shifting e1 to the other side, we define the support slice S as: S := Im(Ay )⊥ + e1 = {ω ∈ Zn2 : ω + e1 ∈ Im(Ay )⊥ }.

(3.50)

1 X H ⊗n |sk ′ ⟩ = √ (−1)(ω+e1 )·by |ω⟩ . 2r ω∈S

(3.51)

Thus, the state simplifies to:

Because we assumed the generic case where the first row of Ay is nonzero, the unit vector e1 is not orthogonal to the column space of Ay , meaning e1 ∈ / Im(Ay )⊥ . Consequently, the shifted subspace S and the original subspace ⊥ Im(Ay ) are completely disjoint: Im(Ay )⊥ ∩ S = ∅.

(3.52)

Hence the Fourier supports of |sk⟩ and |sk ⟩ are completely disjoint. Now we can define a diagonal operator such that ( X 1, if ATy ω = 0, D= ϕ(ω) |ω⟩⟨ω|, ϕ(ω) = (3.53) −1, otherwise. ω∈Zn 2 ′

D can also be written as following, iπ

D=e

|ω⟩⟨ω|

ω ∈Im(A / y )⊥

(3.54)

Combining all these we get XL = H ⊗n DH ⊗n

(3.55)

19 3. Multi-bit Signing Using Iterative Measurements

The one-bit signing algorithm generalizes to l ∼ O(poly(λ)) bits by expanding the transformation matrix. We define (n+l)×(n+l−r) the augmented binary matrix Ãy ∈ Z2 as follows: Ãy =

Il 0 By Ay

(3.56)

n×(n−r)

where By ∈ Zn×l is a matrix of random bits and Ay ∈ Z2 . This matrix acts on a combined vector (w ∥ z) ∈ 2 l+(n−r) (l) (n) n+l Z2 . Given a random shift vector by = (by ∥ by ) ∈ Z2 , the state preparation follows the affine transformation: |ψ⟩ = √

2n+l−r

(n) |w + b(l) y ⟩ |By w + Ay z + by ⟩

(3.57)

w∈Zl2 z∈Zn−r 2

To sign an l-bit message m ∈ Zl2 , the signer measures the first l qubits sequentially. Let pi denote the measurement outcome of the i-th qubit. a. The Iterative Measurement Procedure

• Comparison: If pi = mi , the signer proceeds to measure the (i + 1)-th qubit. • Correction: If pi ̸= mi , the state has collapsed into the “wrong” subspace for the i-th bit. To recover, the signer applies the bit-specific coset subspace flip gate XL,i before proceeding to the next bit. The flip gate is defined as: XL,i = H ⊗(n+l) Di H ⊗(n+l)

(3.58)

As an example let’s discuss what happens when we measure the first qubit and get the wrong measurement, p1 ̸= m1 . (l) The measurement projects the state such that the first bit is fixed to p1 . Since the first register is |w + by ⟩, this (l) restricts the summation to values of w where w1 + (by )1 = p1 . Let w>1 denote the remaining l − 1 free bits of w. The post-measurement state becomes: |ψbad ⟩ = √

1 2n+l−r−1

w∈Zl2

z∈Zn−r 2

(n) |w + b(l) y ⟩ |By w + Ay z + by ⟩

(3.59)

w1 =p1 +(b(l) y )1

The signer applies H ⊗(n+l) to move to the dual space, introducing dual variables u(l) ∈ Zl2 and u(n) ∈ Zn2 : H ⊗(n+l) |ψbad ⟩ = √

X XX X

√

2n+l−r−1 2n+l w1 =p1 w>1

(−1)Φ |u(l) ⟩ |u(n) ⟩

(3.60)

u(l) ,u(n)

where the phase Φ is given by the inner products: (n) Φ = u(l) · (w + b(l) · (By w + Ay z + b(n) y )+u y )

(3.61)

We rearrange the phase to group the terms by the summation variables w and z: Φ = (ATy u(n) ) · z + (u(l) + ByT u(n) ) · w | {z } | {z } (n) =0 forces AT yu

+u |

(l)

splits into w1 and w>1

(n) · b(l) · b(n) y +u y

constant phase

}

The sums over z and the free variables w>1 act as interference filters:

(3.62)

20 • Summing over z ∈ Zn−r evaluates to 0 unless ATy u(n) = 0. 2 • Summing over the l − 1 free bits of w>1 evaluates to 0 unless (u(l) + ByT u(n) )j = 0 for all j ∈ {2, . . . , l}. Crucially, because w1 was fixed by the measurement, there is no sum over w1 . Therefore, the first component of the message constraint is relaxed. (l) The dual state has support only where those constraints are met. For the unconstrained bit, let v1 = u1 + (l) (ByT u(n) )1 ∈ {0, 1}. The phase contribution from the fixed w1 bit becomes (−1)v1 (p1 +(by )1 ) . The state simplifies to: (l)

H ⊗(n+l) |ψbad ⟩ ∝

(l)

(−1)v1 (p1 +(by )1 )+... |u(l) ⟩ |u(n) ⟩

(3.63)

(n)

u ,u (n) AT =0 yu (l)

∀j̸=1, uj =(ByT u(n) )j (l)

Because v1 = u1 + (ByT u(n) )1 is free to take values 0 or 1, the dual state splits evenly across these two values. (l)

(n)

Applying the oracle D1 with the phase (−1)u1 +(By u )1 directly toggles the sign between these two halves, which perfectly corresponds to swapping the primal state from p1 to ¬p1 (the correct message bit m1 ) once the Hadamards are applied again. The operator Di in Eq. 3.58 is defined in the Hadamard (dual) basis. Let u = (l) (u(l) ∥ u(n) ) be the dual variables. Before any measurement, the state satisfies the constraint uj + (ByT u(n) )j = 0 for all j ∈ {1, . . . , l}. If the measurement of the i-th qubit yields an incorrect outcome pi ̸= mi , the state collapses and the i-th primal (l) variable is fixed. This relaxes the corresponding i-th dual constraint. Consequently, the term ui + (ByT u(n) )i takes values 0 and 1 with equal probability across the superposition. We define the phase oracle Di to act on this bit: b. The Dual-Space Phase Oracle Di

(l)

(n)

Di |u(l) ⟩ |u(n) ⟩ = (−1)ui +(By u

|u(l) ⟩ |u(n) ⟩

(3.64)

(l)

Applying Di introduces a −1 phase to the subspace where ui + (ByT u(n) )i = 1. After applying the subsequent Hadamard transforms to return to the primal space, this phase flip corrects the i-th bit from pi to mi . The state of all other coordinates j ̸= i remains unchanged. Because the localized flip operators XL,i = H ⊗(n+l−i) Di H ⊗(n+l−i) commute with the underlying subspace constraints and act as the identity on the logical subspaces of j ̸= i, the iterative procedure successfully forces the first l qubits to match the message m bit-by-bit without disturbing previously measured bits. Once all l bits of the first register match the message m ∈ Zl2 , the first register has collapsed entirely to the classical string m. From the perspective of the initial state preparation, this corresponds to fixing the internal variable w such (l) (l) that w + by = m, which implies w = m + by . Substituting this fixed w into the second register, the state of the remaining n qubits is a pure superposition over the remaining free variables z ∈ Zn−r : 2 c. Signature Extraction

(n)

|ψfinal ⟩ = √

1 2n−r

(n) |By (m + b(l) y ) + A y z + by ⟩

(3.65)

z∈Zn−r 2

The signer then measures these remaining n qubits in the computational basis. The resulting bitstring σ ∈ Zn2 must (l) (n) take the form σ = By (m + by ) + Ay z + by for some z. Rearranging this equation yields the classical verification condition: (l) σ + b(n) y + By (m + by ) = Ay z ∈ Im(Ay )

(3.66)

This confirms that the measured signature σ is valid and consistent with both the message m and the public key y.

21 4. Multi-bit Signing Using Global Measurement and Translation

To sign an l-bit message m ∈ Zl2 using a global approach, the signer performs a simultaneous computational basis measurement of the first l qubits of the state |ψ⟩. Let p ∈ Zl2 denote the observed l-bit measurement outcome. This measurement projects the first register into the state |p⟩, collapsing the remaining unmeasured qubits into the corresponding valid signature subspace for p. If p ̸= m, the signer applies a global translation operator XL to the entire (n+l) qubit post-measurement state to shift the state into the target subspace associated with the message m. The global translation gate is defined as:

a. Global Correction Procedure

XL = H ⊗(n+l) Dp→m H ⊗(n+l)

(3.67)

The oracle Dp→m leverages the Fourier shift theorem to account for the displacement across all l message dimensions simultaneously. Let d = p + m be the l-bit displacement vector. In the dual basis (u(l) , u(n) ), the oracle applies a phase shift proportional to the inner product of the displacement vector and the dual-space constraints:

b. Global Dual Phase Oracle

Dp→m |u(l) ⟩ |u(n) ⟩ = (−1)(u

(l)

+ByT u(n) )·d

(3.68)

|u(l) ⟩ |u(n) ⟩

Expanding the phase term yields u(l) · d + u(n) · By d. Upon applying the subsequent global Hadamard transforms, this phase gradient precisely translates the primal state of the first register by d (mapping p to m) and the entangled second register by By d, satisfying the affine structure of the augmented matrix Ãy . To verify the global translation, we trace the state evolution through the application of XL . 1. Post-Measurement State: When the first register is measured as p ∈ Zl2 , the internal variable w collapses (l) (l) such that w + by = p, which implies w = p + by . The normalized post-measurement state becomes a superposition n−r over the free variables z ∈ Z2 : |ψpost ⟩ = √

2n−r

(n) |p⟩ |By (p + b(l) y ) + A y z + by ⟩

(3.69)

z∈Zn−r 2

2. First Hadamard Transform: Applying H ⊗(n+l) maps the state to the dual space. The summation over z acts as an interference filter, restricting the support to dual variables where ATy u(n) = 0: X

|ψdual ⟩ ∝ u

(−1)Φold |u(l) ⟩ |u(n) ⟩

(3.70)

∈Zl2 , u(n) ∈Zn 2 (n) AT =0 yu

(l)

where the initial dual phase is: (n) Φold = u(l) · p + u(n) · By (p + b(l) y ) + by

(3.71)

3. Applying the Oracle Dp→m : The oracle applies the phase shift (−1)(u the property (ByT u(n) ) · d = u(n) · By d, the new phase Φnew becomes:

(l)

+ByT u(n) )·d

, where d = p + m. Using

Φnew = Φold + u(l) · d + u(n) · By d (n) = u(l) · (p + d) + u(n) · By (p + d) + By b(l) y + by

(3.72)

Since d = p + m, we have p + d = m. Substituting this yields: (n) Φnew = u(l) · m + u(n) · By (m + b(l) y ) + by

(3.73)

22 4. Second Hadamard Transform: The phase Φnew perfectly matches the dual-space representation of a state (l) (n) localized at m in the first register and affine-shifted by By (m + by ) + by in the second register. Applying the final ⊗(n+l) H returns the state to the primal basis: XL |ψpost ⟩ = √

1 2n−r

(n) |m⟩ |By (m + b(l) y ) + Ay z + by ⟩

(3.74)

z∈Zn−r 2

This proves that the first register has been perfectly shifted to the target message m, while the second register remains in a uniform superposition over the valid signature subspace corresponding exactly to m. This global approach reduces quantum circuit depth compared to iterative bit-flipping, requiring only two layers of Hadamard transforms separated by a single phase-kickback oracle. Because the global shift XL acts as a bijective translation, it preserves the uniform superposition, mapping the entire set of valid signatures for p directly onto the set of valid signatures for m. The signer then measures the remaining n qubits in the computational basis to extract the final signature σ, completing the protocol. c. Complexity and Success

F. Verify

As in the original OSS protocol, the verification algorithm in our construction is also a classical, deterministic procedure that checks the validity of the signature σ against a message m and a public key y. This is illustrated in Figure 3. The verification workflow proceeds through a sequence of classical algorithmic steps, leveraging the parameters from the CRS: 1. GGM Tree Path Traversal: Using the public key y and an obfuscated verification program containing the hidden key klin , the verifier performs a classical GGM tree search to resolve the corresponding leaf key. ˜ 2. Graff Inversion (Graff): Using the derived leaf key, the verifier reconstructs the necessary coset parameters (Py−1 , By , by ). The verifier then computes the pre-image coordinate vector z using the message m and the signature component τ via the following matrix computation: z = Py−1 · By · m + b(l) + τ + b(n) y y The inverse matrix Py−1 can be efficiently applied by taking the sequence of gates used in the Graff circuit and inverting it. 3. Validity Constraints: The signature is universally accepted if and only if the outputs of the following two independent comparators both yield true (i.e., evaluated via a logical AND gate): • Zero-Padding Check: The verifier ensures that the last r bits of the computed vector z are all zeros, ? validating that zn−r...n = 0⊗r . • Message Bit Check: The verifier ensures that the first l bits of the signature σ exactly match the signed ? message m, confirming that σ1...l = m. IV. LOGICAL RESOURCES A. Logical qubits

KeyGen and Sign both require enough room for a public key, a signature, a GGM.Lookup, and a Graff. In symbols that is #QOSS = r + n + #QGGM.Lookup + #QGraff ; however, due to the sequential nature of the circuits, there are some gestalt savings available. We calculated above that Graff requires bk + n + 1 qubits. We also know that GGM.Lookup keeps checkpoints in only ⌈− lg(1 − 2−R (r + 1))⌉ of its R := ⌈lg(r + 2)⌉ key registers. This leaves f = R − ⌈− lg(1 − 2−R (r + 1))⌉ free key registers that can be repurposed to satisfy the Graff requirements. Moreover, GGM.Lookup adds an additional

23 2bk qubits when run with small keys. Let Qadd denote the extra qubit overhead required when these repurposed free registers are insufficient to cover the Graff requirements, defined as: εadd = max(bk + n + 1 − f − εsmall keys , 0). Tying this all together gives the total logical qubit count: #QOSS = r + n + Rκ + εadd

(4.1)

The first nine configurations are evaluated and tabulated in Table II. Table II: Logical qubit counts for single-bit-message OSS. 2 3 4 5 6 7 8 9 10 4 12 24 40 60 84 112 144 180 10 21 36 55 78 105 136 171 210 64 64 64 64 96 128 144 192 256 #QOSS 206 289 380 479 745 1 085 1 256 1 851 2 438 λ r n κ

B. Logical gates 1. Key Generation

As stated above, GGM.Lookup has NextKey step complexity Θ(rlg(3) ). Each NextKey circuit makes

X CX Cipher 2 1 1

calls. The Graff gate complexity scales with signature size, and is tabulated in Table III. We lower bound the number of PRG calls necessary to step through the pseudorandom stream. Multiplication by the triangular matrices contributes only to the CCX count. The permutation instructions are decoded into CSWAPs. And the coset shift is implemented by CX gates. Table III: The Graff gate complexity. 2n(n + 1) − 4 X CX n(n + 1) − 2 + n CCX 2n2 − 2 CSWAP (n − 1)n(n + 1)/6 bk PRG Ω(n(3n + 1)/2 − 1)

The KeyGen circuit factors into two GGM.Lookups, one Graff, n Hadamards, and r measurements. The subcircuit resource estimates are combined, evaluated, and tabulated in Table IV. We note that the λ = 9 circuit has a higher total gate count than the λ = 10 circuit; this is because λ = 9 runs a small key GGM.Lookup. Table IV: Gate counts for the KeyGen algorithm λ 2 3 4 5 6 7 8 9 10 r 4 12 24 40 60 84 112 144 180 n 10 21 36 55 78 105 136 171 210 κ 64 64 64 64 96 128 144 192 256 H 10 21 36 55 78 105 136 171 210 X 31 084 139 018 438 078 1 106 092 2 640 302 9 415 012 41 258 684 149 478 128 100 206 816 CX 175 576 787 037 2 487 166 6 298 781 14 508 496 50 691 945 131 321 638 468 369 837 521 750 744 CCX 19 819 89 460 284 792 727 016 1 665 453 5 638 584 22 985 874 80 847 916 55 904 687 226 489 1 015 536 3 210 072 8 131 944 18 814 329 65 745 646 195 566 332 698 696 052 677 862 457

24 2. Signing

Recall that a measurement on the first qubit of a coset state collapses the sum into a collection of subterms with the same leading bit. Applying an Equivocate circuit switches between these collections. The circuit Equivocate is the circuit realization for the global dual phase oracle Dp→m . And we use Gr* to denote the circuit that applies the transpose of the linear part of Graff. An Equivocate circuit requires, ∥Equivocate∥Gates = 2∥GGM.Lookup∥Gates + 2∥Gr*∥Gates + 2nH + 2(n − r)X + 2Cn−r X + Z The Cj X gate can further be decomposed to 2j − 3 CCX and 2j − 6 X gates and a clean ancilla qubit (KG25). The signing routine requires an equivocation half the time, giving an expected gate count: E∥Sign∥Gates = nMeasure + ∥Equivocate∥Gates /2

Table V: Gate counts for single-bit-message Sign that equivocates. λ 2 3 4 5 6 7 8 9 10 r 4 12 24 40 60 84 112 144 180 n 10 21 36 55 78 105 136 171 210 κ 64 64 64 64 96 128 144 192 256 H 20 42 72 110 156 210 272 342 420 X 42 692 183 828 573 966 1 419 262 3 382 370 11 124 478 44 956 900 157 079 426 112 008 600 CX 240 516 1 039 388 3 259 712 8 099 068 18 655 968 60 123 560 143 740 044 493 581 148 585 557 868 954 374 2 193 948 6 827 966 25 443 198 85 776 062 63 886 288 CCX 27 368 119 558 379 162 Z 1 1 1 1 1 1 1 1 1 310 597 1 342 817 4 212 913 10 472 815 24 232 443 78 076 215 214 140 415 736 436 979 761 453 177

C. Logical resources for multi-bit signing

Generalizing to longer messages requires 2l additional qubits: l to store the signature, and another l ancilla qubits for the global measurement protocol. We add this to our earlier analysis in Eq. 4.1 to arrive at, #Q = n + 2l + r + κ⌈lg(r + 2)⌉

(4.2)

To calculate the extra gates required for both key generation and signing, we will now go through each step of the protocol. • Hadamards: Since the signature size is n + l instead of n, we will need l extra Hadamards for this step. • GGM.Lookup: This step only depends on the size of public key (r) and not on the signature size. So the number of gates remain the same. nl • Graff: We need nl extra random bits to perform the action of By . This requires ⌈ bk ⌉ calls to PRG. To realize extra matrix multiplications in the Bruhat decomposition, we need an extra nl CCX and l CX gates.

• Sign: The number of extra gates/calls required scales as follows #GGM.Lookup 2 H 2l X l CX 2l CCX nl bk PRG nl

25 V. CONCRETE SECURITY A. Parameter choice and discussion on possible attacks

Let λ ∈ N be the statistical security parameter. Recall that the OSS Construction 52 in Shmueli and Zhandry’s work (SZ25a) defines the following parameters in terms of λ: n, r, k, s, d, κ. The parameters n, r, k, s determine the sizes and dimensions of subspaces and cosets while κ determines the security level of the underlying pseudorandom function. These parameters are chosen to be sufficiently large to prevent efficient collision finding in the oracle based construction. In the corresponding plain-model construction, indistinguishability obfuscation (iO) is used to translate oracle-based security into plain-model security. In this setting, the cryptographic security parameter κ plays a central role and must be selected carefully. Note that the values of the structural parameters s, r, n, k remain unchanged, regardless of whether obfuscation is used. One subtle point is that (SZ25a) use λ to describe the statistical security of their constructions. This parameter may be roughly interpreted as an efficient adversary’s success probability of finding collisions for the underlying non-collapsing hash function. In this work, since the information of the (KeyGen, Sign, Verify) algorithms, including the oracles P , P −1 , and D, will be published in obfuscated forms, an adversary can use any of these oracles to perform attacks. Here, we focus on the values for r and κ and only discuss the best possible attacks by both classical and quantum adversaries: • r: Determines the number of possible hash digests (and public keys) y ∈ {0, 1}r . – A classical adversary can use the verification circuit containing the oracles P −1 with the information of the public key y to find two pairs of valid signatures with the same public key, running P −1 (y, u) until he finds x such that P −1 (y, u) = (x∥0r ). The probability of finding such a valid u becomes high after trying 2n ) = O(2r ) inputs. O( 2n−r – In the quantum case, the adversary can prepare a superposition of all n-bit strings together with the P known public key as follows: x∈{0,1}n |x⟩ |y⟩. Using the quantisation of the classical verification circuit, the adversary can run Grover’s algorithm to find a valid signature in approximately O(2r/2 ) steps. Therefore, r must be scaled sufficiently large with the security parameter λ so that both attack complexities, O(2r ) classically and O(2r/2 ) quantumly, are computationally infeasible. If r is too small, an adversary can efficiently run either of these processes to find valid signatures under the same public key y. Noting that the messages is the first bit of the signature, by repeating the aforementioned process, the adversary may produce either a collision - two valid signatures on the same message - which breaks the security of the underlying hash function, or multiple valid message-signature pairs on distinct messages, hence violating the one-shot property. • κ: controls the security of the underlying pseudorandom function. If κ is small, a quantum adversary can recover the PRF key klin using Grover search in O(2κ/2 ) oracle queries. The knowledge of klin allows the adversary to reconstruct the coset description (Ay , by ) and regenerate the valid coset states, hence creating additional valid signatures on the same message. We now discuss our choice for the cryptographic security parameter κ. Assume that all cryptographic building blocks δ are subexponentially secure for a subexponential (in λ) function f (λ) = 2λ with 0 < δ < 1. Note that the security of the protocol in the plain model construction relies on a carefully chosen parameter set that guarantees the following: for any PPRF key of size κ, and for the total number of cosets 2r —which is also the number of possible hash digests y—the Bloating the Dual technique ensures that each coset Cy is embedded into a superspace Ty with Cy ⊆ Ty ⊆ Zk2 . Under this construction, the value of κ is derived using the bound given in (SZ25a, Lemma 26, Lemma 56) guarantee that an adversary A cannot tamper with the obfuscated circuit associated with these superspaces in order to exploit the collisions of the underlying hash function: 2

2r · kϵ 1 ≤ f (κ) 512 κ ≥ (9 + 2λ(λ − 1) + λδ + 2 lg(2λ2 + λ))1/δ Appropriate values of κ for varying λ can be found in Table II.

(5.1) (5.2)

26 B. Obfuscation 1. Classical iO

Classical indistinguishability obfuscation (iO) is best viewed as the viable relaxation of general program obfuscation that survived Barak et al.’s impossibility result for virtual-black-box obfuscation (Bar12); Goldwasser and Rothblum (GR07) further showed that, for efficient obfuscators, iO is equivalent to best-possible obfuscation. The first candidate for all circuits was given by Garg et al. (Gar16), but the early multilinear-map era came with severe polynomial overhead. For a size-s fan-out-1 circuit (i.e., Boolean formula), standard Barrington-style preprocessing already yields a branching program of length s3.64 , and Ananth et al. (Ana14) analyze a line of constructions whose obfuscation size was O(s10.92 ) under a quadratic-cost assumption before being improved to O(s5 ). To overcome the inherent restrictions and conversion overheads of formula-based obfuscation, subsequent works bootstrapped iO to more general computational models. Bitansky and Vaikuntanathan (BV18) showed how to obtain iO from sufficiently succinct functional encryption with obfuscation size 2|C| + poly(λ, d, n) for any circuit C, where λ is the security parameter, d is circuit depth and n is input length, while Ananth, Jain, and Sahai (Ana17) obtained bounded-input (by L) iO with size 2|M | + poly(λ, L) for any Turing machine M . A major conceptual milestone was then achieved by Jain, Lin, and Sahai (Jai26), who established iO for all polynomial-size circuits from well-founded assumptions, albeit at the level of general polynomial overhead rather than near-linear efficiency. Along this line, Ragavan et al. (Rag25) simplified the assumption set by removing the need for polynomial-stretch NC0 pseudorandom generators. More recent work has improved efficiency in structured settings instead of merely proving existence. Jain and Jin (JJ22) removed the exponential loss in the input length whenever functional equivalence admits short propositional proofs, Ma, Dai, and Shi (Ma,25) further reduced the resulting obfuscation and evaluation complexity to quasi-linear in the circuit size and proof size. Parallely, Diamond iO (Sor25) simplified lattice-based iO by replacing costly recursive encryption with lightweight matrix operations, maintaining an O(L) overhead with respect to the input length while bounding the overall obfuscation size by standard poly(|C|). Notably, a recent work by Jain et al. (Jai25) introduced fully succinct iO, which demonstrates that the size of the obfuscated program grows only with the program’s secret part, remaining completely independent of the public description and input size. Consequently, this provides an affordable means to obfuscate the puncturable PRF key klin within the classical portion of our one-shot signature. Overall, the literature suggests a clear spectrum, i.e., while unrestricted classical iO remains a high-degree-polynomial object, structured variants can already be quasi-linear, or even more efficient in the case that only a small classical secret subprogram needs to be hidden. This makes classical iO a plausible choice in our setting, as the resulting overhead can reasonably be expected to remain tolerable. We will discuss it in detail in Sec. V.B.3.

2. Quantum iO

Quantum iO is substantially less mature than classical iO. Alagic and Fefferman (Ala16) formalized several notions of quantum obfuscation and proved strong impossibility results, showing that generic quantum black-box obfuscation fails once an adversary can obtain multiple obfuscated copies, and statistical indistinguishability obfuscation would imply an unlikely complexity collapse. Alagic et al. (Ala21) later showed that even quantum virtual-black-box obfuscation of classical circuits is generally impossible under quantum-hard LWE. Positive results therefore began only for highly restricted classes. Broadbent and Kazmi (Bro21) obtained a construction whose size is exponential in the number of T gates and hence efficient only for a Clifford+T circuit C with T-count O(log |C|). Subsequent work primarily expanded the class of quantum circuits that can be obfuscated, rather than improving the asymptotic efficiency of the constructions. Bartusek et al. (Bar23) obtained obfuscation for polynomial-size pseudo-deterministic quantum circuits in the classical-oracle model; Coladangelo and Gunn (Col24) introduced quantum state iO, showed that it yields best-possible copy protection for all programs, but only relative to an efficient quantum oracle; and Bartusek, Brakerski, and Vaikuntanathan (Bar24) constructed quantum state obfuscation for pseudo-deterministic quantum programs in the classical-oracle model, heuristically instantiable from quantum-secure classical iO. Huang and Tang (Hua25) then extended the scope to unitary (and approximately unitary) quantum programs with quantum inputs and outputs in the classical-oracle model, and the same authors in a very recent preprint (Hua26) further claims the first universal obfuscation for arbitrary quantum circuits with quantum inputs and outputs in the classical-oracle model, with a corollary in the quantumly accessible pseudorandom-oracle model from post-quantum subexponential one-way functions and functional encryption.

27 3. Hiding the GGM master key using fully succinct obfuscation

Jain, Jin, Mathialagan, and Paneth (Jai25) introduce a fully succinct obfuscation notion for Turing machines with split descriptions. In this syntax, a program is written as M [pub], where pub is a public part that may be large, while M is the secret part that we wish to protect. The fully succinct guarantee says that the size of the obfuscated program grows only with the size of the secret part M , and not with the public part pub or the input length. This is exactly the setting applicable to our PPRF construction, as the algorithms for GGM evaluation, puncturing, and the subsequent linear-algebraic post-processing are public, while the value we want to hide is the GGM master key klin . To this end, we only need the fully succinct EF-iO, or equivalently the fully succinct pv-iO, guaranteed in (Jai25), rather than general iO for all equivalent machines. Indeed, the two programs we transition between below are not arbitrary equivalent programs: their equivalence follows from the PV correctness of GGM puncturing by (Jai25, Lemma IV.12). We now verify the required EF-equivalence condition. Let Fmaster be the GGM evaluation algorithm we use to construct our PPRF. Let Post(y, ky , pub) = (Ay , by ) denote the deterministic polynomial-time post-processing algorithm used by our construction. Specifically, Post takes the point y, the GGM leaf key ky := Fmaster (klin , y), and public parameters pub, and returns the matrix-vector pair (Ay , by ). We note that all randomness used by the post-processing is derived deterministically from the GGM output ky . Thus Post is a deterministic polynomial-time computation and can be formalized in PV. Fix a puncturing set S ⊆ {0, 1}r , let k S be the punctured key, and define the table of punctured values as ∆S := {(y, ky ) : y ∈ S, ky = Fmaster (klin , y)}. We use ∆S [y] to denote the table lookup value ky for y ∈ S. The set S is treated as part of the public description. The original PPRF program with the master key is Mmaster [pub, S](y) := Post(y, Fmaster (klin , y), pub). The corresponding PPRF program with the punctured key is ( Post(y, ∆S [y], pub), Mpunc [pub, S](y) := Post(y, Fpunc (k S , y), pub),

if y ∈ S, if y ∈ / S.

(5.3)

(5.4)

Here Fpunc denotes the punctured GGM evaluation algorithm. Now we show that the two programs Mmaster [pub, S] and Mpunc [pub, S] agree on every input y ∈ {0, 1}r . The proof is by case analysis. First, we suppose y ∈ / S. By (Jai25, Lemma IV.12), the standard GGM construction of PPRF has a PV proof of puncturing correctness. Thus PV proves y∈ /S

=⇒

Fpunc (k S , y) = Fmaster (klin , y).

(5.5)

Since Post is deterministic polynomial-time and formalizable in PV, PV is closed under substituting equal terms into Post. Therefore PV also proves y∈ /S

=⇒

Post(y, Fpunc (k S , y), pub) = Post(y, Fmaster (klin , y), pub).

(5.6)

Hence y∈ /S

=⇒

Mpunc [pub, S](y) = Mmaster [pub, S](y).

(5.7)

Now suppose y ∈ S. By construction of the table ∆S , we have ∆S [y] = Fmaster (klin , y).

(5.8)

Again, substituting this equality into the deterministic PV-formalizable function Post, PV proves y∈S

=⇒

Post(y, ∆S [y], pub) = Post(y, Fmaster (klin , y), pub).

(5.9)

=⇒

(5.10)

Therefore y∈S

Mpunc [pub, S](y) = Mmaster [pub, S](y).

Combining the two cases, PV proves for every input y ∈ {0, 1}r , Mpunc [pub, S](y) = Mmaster [pub, S](y).

(5.11)

28 By the propositional translation theorem for PV (see (Jai25, Theorem IV.2), following Cook (Coo75) and Cook– Reckhow (CR79)), this PV proof yields a uniform polynomial-size EF proof of the statement ∀y ∈ {0, 1}r ,

Mpunc [pub, S](y) = Mmaster [pub, S](y).

(5.12)

Hence the two split-description programs are uniformly EF-equivalent. Finally, the formal definition of fully succinct EF-iO requires the two programs to have the same description length and the same running time. We satisfy this by standard padding: we pad the shorter secret description with dummy bits, and we pad the faster computation with dummy steps. This padding does not change the functionality of either program and is itself PV-formalizable. Therefore, the padded versions of Mmaster [pub, S] and Mpunc [pub, S] satisfy the same-size, same-runtime, and uniform-EF-equivalence conditions required for fully succinct EF-iO. Corollary 4 (Obfuscating without exposing the PPRF master key). The program Mmaster contains the original GGM master key klin , whereas Mpunc contains only the punctured key k S and the table of punctured values ∆S . Thus, the obfuscation of the PPRF program with a master key is computationally indistinguishable from the obfuscation of an equivalent program whose secret description no longer contains klin by the fully succinct EF-iO in (Jai25). 4. Conditional quantum obfuscation component

We stress that the obfuscation step used for hiding the classical GGM/PPRF master key klin is purely classical. In particular, the corresponding master-key and punctured-key programs are classical split-description Turing machines, and their equivalence is certified by the PV correctness of GGM puncturing. Hence this part can be handled by the fully succinct EF-iO/pv-iO machinery of (Jai25). The situation is different for the main one-shot signature construction proposed in this work. In the original oneshot signature paradigm, the obfuscated object is classical, for instance a suitable obfuscation of a pseudorandom permutation or a permutable PRP, and classical iO is sufficient for this purpose. In our variant, however, we replace the classical PPRP layer by a quantum procedure involving Hadamard gates. As a result, the object that must be hidden is no longer a purely classical program, but a quantum circuit. Classical iO does not apply to such a circuit-level quantum functionality. To instantiate this part of our construction, one would need a quantum indistinguishability obfuscator for the relevant class of Hadamard-based quantum circuits. At present, we therefore view this quantum one-shot signature component as a conditional and forward-looking instantiation. Existing quantum obfuscation results provide important evidence that quantum iO is a meaningful theoretical primitive, but they do not yet yield a practical plain-model implementation suitable for our scheme. Thus, our construction separates the currently implementable classical obfuscation layer from the quantum obfuscation layer that remains conditional on future progress in efficient quantum iO. Once such an efficient quantum iO primitive becomes available, the present construction can be instantiated by applying classical fully succinct iO to the GGM/PPRF component and quantum iO to the Hadamard-based signing component. VI. CONCLUSIONS

We have presented an explicit quantum-circuit implementation of a one-shot signature scheme, translating recent protocol-level constructions into concrete algorithms for KeyGen, Sign, and Verify. The construction prepares the quantum signing key as a uniform superposition over a hidden affine coset determined by a puncturable pseudorandom function, and realizes the required arithmetic using a GGM-based lookup together with reversible linear-algebra subroutines. We also introduced a streamlined signing procedure for l-bit messages, replacing the repeated single-bit signing structure with a global measurement and a single translation step. Our resource analysis shows that the resulting implementation has logical qubit complexity scaling as Θ(κ log r +n + l) and gate complexity scaling as Θ(n3 + nl), thereby making explicit the dominant costs and their dependence on the security and message-size parameters. From a security perspective, the construction should be viewed as a concrete algorithmic implementation of the unobfuscated OSS protocol, together with an identification of the components that must be hidden to obtain the intended one-shot guarantee. Classical obfuscation techniques can address the purely classical PPRF/GGM subroutines, but the modified key generation step requires an obfuscator for the relevant class of quantum circuits. Thus, this work clarifies both the practical algorithmic structure of OSS and the remaining bottleneck for a full plain-model instantiation: the development of efficient and secure quantum obfuscation tools. We expect the circuit-level perspective developed here to be useful for future implementations of unclonable cryptographic primitives, including delegated signatures, quantum tokens, quantum money, and publicly verifiable randomness.

29 VII. ACKNOWLEDGEMENTS

We acknowledge helpful discussions with Steven Duong.

REFERENCES [AC12] Scott Aaronson and Paul Christiano. Quantum money from hidden subspaces. In Proceedings of the Forty-Fourth Annual ACM Symposium on Theory of Computing, STOC ’12, page 41–60, New York, NY, USA, 2012. Association for Computing Machinery. [AGKZ20] Ryan Amos, Marios Georgiou, Aggelos Kiayias, and Mark Zhandry. One-shot signatures and applications to hybrid quantum/classical authentication. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, page 255–268, New York, NY, USA, 2020. Association for Computing Machinery. [Ala16] Alagic, Gorjan and Fefferman, Bill. On quantum obfuscation. arXiv preprint arXiv:1602.01771, 2016. [Ala21] Alagic, Gorjan and Brakerski, Zvika and Dulek, Yfke and Schaffner, Christian. Impossibility of quantum virtual black-box obfuscation of classical circuits. In Annual International Cryptology Conference, pages 497–525. Springer, 2021. [AMM20] Ravi Anand, Arpita Maitra, and Sourav Mukhopadhyay. Grover on SIM ON . Quantum Information Processing, 19(9):340, 2020. [Ana14] Ananth, Prabhanjan and Gupta, Divya and Ishai, Yuval and Sahai, Amit. Optimizing obfuscation: avoiding barrington’s theorem. In Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security, pages 646–658, 2014. [Ana17] Ananth, Prabhanjan and Jain, Abhishek and Sahai, Amit. Indistinguishability obfuscation for turing machines: constant overhead and amortization. In Annual International Cryptology Conference, pages 252–279. Springer, 2017. [Bar12] Barak, Boaz and Goldreich, Oded and Impagliazzo, Russell and Rudich, Steven and Sahai, Amit and Vadhan, Salil and Yang, Ke. On the (im)possibility of obfuscating programs. J. ACM, 59(2), May 2012. [Bar23] Bartusek, James and Kitagawa, Fuyuki and Nishimaki, Ryo and Yamakawa, Takashi. Obfuscation of pseudodeterministic quantum circuits. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, pages 1567–1578, 2023. [Bar24] Bartusek, James and Brakerski, Zvika and Vaikuntanathan, Vinod. Quantum state obfuscation from classical oracles. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing, pages 1009–1017, 2024. [BDJ+ 24] Pedro Branco, Nico Döttling, Abhishek Jain, Giulio Malavolta, Surya Mathialagan, Spencer Peters, and Vinod Vaikuntanathan. Pseudorandom obfuscation and applications. Cryptology ePrint Archive, Paper 2024/1742, 2024. [BDS23] Shalev Ben-David and Or Sattath. Quantum Tokens for Digital Signatures. Quantum, 7:901, January 2023. [Ben89] Charles H. Bennett. Time/space trade-offs for reversible computation. SIAM J. Comput., 18(4):766–776, August 1989. [BJJ+ 25] Nikhil Bartake, See Toh Zi Jie, Carmen Wong Jiawen, Michael Kasper, and Vivek Balachandran. Obfusqate: Unveiling the first quantum program obfuscation framework, 2025. [BKL+ 07] A. Bogdanov, L. R. Knudsen, G. Leander, C. Paar, A. Poschmann, M. J. B. Robshaw, Y. Seurin, and C. Vikkelsoe. Present: An ultra-lightweight block cipher. In Pascal Paillier and Ingrid Verbauwhede, editors, Cryptographic Hardware and Embedded Systems - CHES 2007, pages 450–466, Berlin, Heidelberg, 2007. Springer Berlin Heidelberg. [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 Proceedings of the 57th Annual ACM Symposium on Theory of Computing, pages 201–212, 2025. [Bro21] Broadbent, Anne and Kazmi, Raza Ali. Constructions for quantum indistinguishability obfuscation. In International Conference on Cryptology and Information Security in Latin America, pages 24–43. Springer, 2021. [BTCS+ 15] Ray Beaulieu, Stefan Treatman-Clark, Douglas Shors, Bryan Weeks, Jason Smith, and Louis Wingers. The simon and speck lightweight block ciphers. In 2015 52nd ACM/EDAC/IEEE Design Automation Conference (DAC), pages 1–6, 2015. [BV18] Nir Bitansky and Vinod Vaikuntanathan. Indistinguishability obfuscation from functional encryption. Journal of the ACM (JACM), 65(6):1–37, 2018. [CCJ+ 16] Lily Chen, Stephen Chen, Stephen Jordan, Yi-Kai Liu, Dustin Moody, Rene Peralta, Ray Perlner, and Daniel SmithTone. Report on post-quantum cryptography. National Institute of Standards and Technology Internal Report, 8105:1–15, 2016. [CGS25] Alper Cakan, Vipul Goyal, and Omri Shmueli. Public-key quantum fire and key-fire from classical oracles. arXiv preprint arXiv:2504.16407, 2025. [CLLZ22] Andrea Coladangelo, Jiahui Liu, Qipeng Liu, and Mark Zhandry. Hidden cosets and applications to unclonable cryptography, 2022. [CNS26] Ofer Casper, Barak Nehoran, and Or Sattath. Publicly certifiable min-entropy without quantum communication. Cryptology ePrint Archive, 2026. [Col24] Coladangelo, Andrea and Gunn, Sam. How to use quantum indistinguishability obfuscation. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing, pages 1003–1008, 2024. [Coo75] Stephen A. Cook. Feasibly constructive proofs and the propositional calculus. In Proceedings of the Seventh Annual ACM Symposium on Theory of Computing, pages 83–97. ACM, 1975.

30 [CR79] Stephen A. Cook and Robert A. Reckhow. The relative efficiency of propositional proof systems. Journal of Symbolic Logic, 44(1):36–50, 1979. [CS20] Andrea Coladangelo and Or Sattath. A quantum money solution to the blockchain scalability problem. Quantum, 4:297, July 2020. [Cur79] Charles W. Curtis. Representations of finite groups of Lie type. Bulletin (New Series) of the American Mathematical Society, 1(5):721 – 757, 1979. [Gar16] Garg, Sanjam and Gentry, Craig and Halevi, Shai and Raykova, Mariana and Sahai, Amit and Waters, Brent. Candidate indistinguishability obfuscation and functional encryption for all circuits. SIAM Journal on Computing, 45(3):882–929, 2016. [GGM86] Oded Goldreich, Shafi Goldwasser, and Silvio Micali. How to construct random functions. J. ACM, 33(4):792–807, August 1986. [GO12] Alexander Gnedin and Grigori Olshanski. The two-sided infinite extension of the mallows model for random permutations. Advances in Applied Mathematics, 48(5):615–639, 2012. [GR07] Shafi Goldwasser and Guy N Rothblum. On best-possible obfuscation. In Theory of Cryptography Conference, pages 194–213. Springer, 2007. [Gro96] Lov K Grover. A fast quantum mechanical algorithm for database search. In Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, pages 212–219, 1996. [Hua25] Huang, Mi-Ying Miryam and Tang, Er-Cheng. Obfuscation of unitary quantum programs. In 2025 IEEE 66th Annual Symposium on Foundations of Computer Science (FOCS), pages 1665–1671. IEEE, 2025. [Hua26] Huang, Miryam Mi-Ying and Tang, Er-Cheng. Obfuscation of arbitrary quantum circuits. arXiv preprint arXiv:2601.08969, 2026. [HV25] Andrew Huang and Vinod Vaikuntanathan. A simple and efficient one-shot signature scheme, 2025. [Jai25] Jain, Abhishek and Jin, Zhengzhong and Mathialagan, Surya and Paneth, Omer. On succinct obfuscation via propositional proofs. In 2025 IEEE 66th Annual Symposium on Foundations of Computer Science (FOCS), pages 1703–1740. IEEE, 2025. [Jai26] Jain, Aayush and Lin, Huijia and Sahai, Amit. Indistinguishability obfuscation from well-founded assumptions. Journal of the ACM, 73(1):1–30, 2026. [JJ22] Abhishek Jain and Zhengzhong Jin. Indistinguishability obfuscation via mathematical proofs of equivalence. In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pages 1023–1034. IEEE, 2022. [JJMP25] Abhishek Jain, Zhengzhong Jin, Surya Mathialagan, and Omer Paneth. On Succinct Obfuscation via Propositional Proofs . In 2025 IEEE 66th Annual Symposium on Foundations of Computer Science (FOCS), pages 1703–1740, Los Alamitos, CA, USA, December 2025. IEEE Computer Society. [JSK+ 21] Kyungbae Jang, Gyeongju Song, Hyunjun Kim, Hyeokdong Kwon, Hyunji Kim, and Hwajeong Seo. Efficient implementation of present and gift on quantum computers. Applied Sciences, 11(11), 2021. [KG25] Tanuj Khattar and Craig Gidney. Rise of conditionally clean ancillae for efficient quantum circuit constructions. Quantum, 9:1752, May 2025. [KL07] Jonathan Katz and Yehuda Lindell. Introduction to modern cryptography: principles and protocols. Chapman and hall/CRC, 2007. [LS25] Donald Lushi and Samah Mohamed Saeed. Undermining quantum circuit obfuscation: Insights from structural analysis. In 2025 IEEE International Symposium on Hardware Oriented Security and Trust (HOST), pages 88–98, 2025. [Ma,25] Ma, Yaohua and Dai, Chenxin and Shi, Elaine. Quasi-linear indistinguishability obfuscation via mathematical proofs of equivalence and applications. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 157–186. Springer, 2025. [MAL57] C. L. MALLOWS. Non-null ranking models. i. Biometrika, 44(1-2):114–130, 06 1957. [MDS25] Yaohua Ma, Chenxin Dai, and Elaine Shi. Quasi-linear indistinguishability obfuscation via mathematical proofs of equivalence and applications. Cryptology ePrint Archive, Paper 2025/307, 2025. [PRS+ 25] Tirthak Patel, Aditya Ranjan, Daniel Silver, Harshitta Gandhi, William Cutler, and Devesh Tiwari. Opaque: Program output obfuscation for quantum software circuits in quantum clouds. In Proceedings of the 39th ACM International Conference on Supercomputing, ICS ’25, page 1079–1091, New York, NY, USA, 2025. Association for Computing Machinery. [Rag25] Ragavan, Seyoon and Vafa, Neekon and Vaikuntanathan, Vinod. Indistinguishability obfuscation from bilinear maps and lpn variants. In Theory of Cryptography Conference, pages 3–36. Springer, 2025. [Sat22] Or Sattath. Quantum prudent contracts with applications to bitcoin, 2022. [Shm22] Omri Shmueli. Public-key quantum money with a classical bank. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2022, page 790–803, New York, NY, USA, 2022. Association for Computing Machinery. [Sho94] Peter W Shor. Algorithms for quantum computation: discrete logarithms and factoring. In Proceedings 35th annual symposium on foundations of computer science, pages 124–134. Ieee, 1994. [Sho99] Peter W Shor. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM review, 41(2):303–332, 1999. [Sor25] Sora Suegami and Enrico Bottazzi and Gayeong Park. Diamond iO: A straightforward construction of indistinguishability obfuscation from lattices. Cryptology ePrint Archive, Paper 2025/236, 2025. [SW13] Amit Sahai and Brent Waters. How to use indistinguishability obfuscation: Deniable encryption, and more. Cryptology ePrint Archive, Paper 2013/454, 2013.

31 [SZ25a] Omri Shmueli and Mark Zhandry. On one-shot signatures, quantum vs. classical binding, and obfuscating permutations. In Advances in Cryptology – CRYPTO 2025: 45th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 17–21, 2025, Proceedings, Part II, page 350–383, Berlin, Heidelberg, 2025. Springer-Verlag. [SZ25b] Omri Shmueli and Mark Zhandry. Unclonable cryptography in linear quantum memory, 2025. [Wie83] Stephen Wiesner. Conjugate coding. SIGACT News, 15(1):78–88, January 1983. [WZ82] William K Wootters and Wojciech H Zurek. A single quantum cannot be cloned. Nature, 299(5886):802–803, 1982. [Zha16] Mark Zhandry. Recent developments in program obfuscation. https://mzhandry.github.io/courses/ 2016-Fall-COS597C/, 2016. Accessed: 2025-06-24. [Zha21] Mark Zhandry. Quantum lightning never strikes the same state twice. or: Quantum money from cryptographic assumptions. J. Cryptol., 34(1), January 2021.

Record · ID 299807 · SHA-256 9dee367b00621b27
Retrieved via Conceptio — every document is proof-bundled with source, license, and retrieval metadata.