1 Introduction↩︎

The study of quantum algorithms is frequently framed within the context of computational complexity, where seminal protocols, such as Grover’s algorithm [1] and Shor’s algorithm for integer factorization and breaking Elliptic Curve Cryptography (ECC) [2], [3], 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 [4]. 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 [5] and measurement-induced 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 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) [6], 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 [6] 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 [7] and [8] repaired the proof and provided the first concrete construction of an OSS. Later that year, Huang and Vaikuntanathan [9] 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 [10] 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 [9].

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) [11], and tokenized signatures [12] became within reach. Coladangelo, Liu, Liu, and Zhandry [13] 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 [11]. 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 [7], [14]. This connection also motivated a concrete line of work on quantum payment schemes. Coladangelo and Sattath [15] showed that quantum money can replace a public ledger to address blockchain scalability. Building on this, Sattath [16] 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 [17]–[19], 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 [18].

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 [20]. 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 [21], [22]. This approach generally relies on structural complexity and heuristic techniques rather than 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 [23]. The second category, post-quantum iO [24]–[27], 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-of-the-art work has achieved a quasilinear blow-up compared to the size of the original circuit [27], 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 2 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 3, we detail our concrete algorithmic implementation, providing explicit quantum circuit constructions and workflows for key generation, multi-bit signing, and classical verification. Section 4 presents a comprehensive logical resource analysis, detailing the qubit requirements and gate complexities of our proposed circuits. Finally, Section 5 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 6.

2 Background↩︎

One can think of a One-Shot Signature (OSS) scheme as an asymmetric digital signature scheme satisfying the one-shot 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 \(\mathsf{negl}(x)\) to denote the class of functions that falls off faster than the inverse of any polynomial [28].

Since this work focuses on the unobfuscated OSS construction, we concentrate attention on the three core algorithms, \((\mathrm{\small KeyGen}, \mathrm{\small Sign}, \mathrm{\small Verify})\).

2.1 High-level structure of the SZ25 OSS protocol↩︎

2.1.1 Setup↩︎

[7] builds the scheme above from three circuits, \(P\), \(P^{-1}\), and \(D\), derived from the common reference string returned by \(\mathrm{\small 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) \(\Pi: \mathbb{Z}_2^n \rightarrow \mathbb{Z}_2^n\), which for clarity we write as \(\Pi(x) = (y,z)\), with \(y\in\mathbb{Z}_2^r\) and \(z\in\mathbb{Z}_2^{n-r}\). The second is a puncturable pseudorandom function (PPRF), \(F:\mathbb{Z}_2^{r} \rightarrow \text{Graff}_{\mathbb{Z}_2}(n-r,n); y \overset{F}\mapsto (A_y, b_y)\), that produces an affine Grassmannian over \(\mathbb{Z}_2\), where we denote the affine Grassmannian by the matrix–vector pair that maps \(\mathbb{Z}_2^{n-r}\) into the \(\mathbb{Z}_2^n\) subspace. The pseudorandom function key of size \(\kappa\) is hardwired into 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 \(\Pi(x) = (y, z)\), and \(F(y) = (A_y, b_y)\), then \(P(x) = (y, A_yz + b_y) =: (y_x, u_x)\). We will refer to these tuple elements as the hash and the coset point. The circuit \(P^{-1}: \mathbb{Z}^r_2\times\mathbb{Z}^n_2\rightarrow\mathbb{Z}^n_2\cup\{\bot\}\) is in essence the inverse of \(P\) extended onto \(\mathbb{Z}_2^n\). It returns \(\bot\) 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: \mathbb{Z}^r_2\times\mathbb{Z}^n_2 \rightarrow \{0,1\}\) and tests, for a given \(y\) and \(u\), whether \(A^T_y u = 0\).

2.1.2 Key generation↩︎

A high level view of the key generation is a program like the following. ¹ \[\begin{align} \mathrm{\small KeyGen}: & \xrightarrow{\mathrm{\small Reset}} |0^{n+r+k}\rangle \\ & \xrightarrow{H^{\otimes n}} |X|^{-1/2}\sum_{x\in X} |x, 0^{r+k}\rangle \\ & \xrightarrow{P} |X|^{-1/2}\sum_{x\in X} |x, y_x, u_x\rangle \\ & \xrightarrow{P^{-1}} |X|^{-1/2}\sum_{x\in X} |0, y_x, u_x\rangle \\ & \xrightarrow{\text{Measure}} |X'|^{-1/2}|0,y\rangle \sum_{x\in X'} |u_x\rangle \end{align}\]

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.

2.1.3 Signing↩︎

A valid signature for public key, \(y\), is any point in the secret coset, \(C_y := b_y + \operatorname{Im}(A_y)\) where \(\operatorname{Im}(A_y) = \{ A_y z : z\in\mathbb{Z}_2^{(n-r)}\}\). Given such a point, \(u\), we interpret it as a signature for bit \(b\) if \(u_1 = b\). The algorithm \(\mathrm{\small Sign}(y, |sk_y\rangle, b)\) generates this value by performing an adapted Amplitude Amplification on the secret key state, and measuring the secret key state [6].

2.1.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 \(\sigma\), 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 \(\sigma\), 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, \sigma) \neq \bot\).

2. Message Binding: The first bit of the signature \(\sigma\) matches the signed message bit \(m\).

2.2 A streamlined construction for OSS↩︎

The construction of Shmueli and Zhandry [7] 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 \(\Pi\) 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 \(\Pi\) 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 space is \(\mathbb{Z}_2^n\). Since \(|+\rangle^{\otimes n}\) is an eigenstate of any permutation \(\Pi\), applying \(\Pi\) to the uniform superposition leaves the state invariant. Concretely, whereas the original \(\mathrm{\small KeyGen}\) applies \(\Pi\) to the uniform superposition before passing it to \(F\) and the linear arithmetic component, our modified \(\mathrm{\small KeyGen}\) algorithm replaces this step entirely with \(H^{\otimes 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; \(\Pi\) 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 \(\Pi\) inside each program is omitted while the PPRF \(F\) and the linear arithmetic component remain unchanged. This modification of omitting \(\Pi\) 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 of the secret-key state by running the key generation algorithm on the initial state of the form \(H^{\otimes (n-r)}|0\rangle^{\otimes (n-r)}|y\rangle\), 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 5 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.

2.3 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 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 [12] 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 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 [29]. 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 [7], [14], 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 [30], 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 [17]–[19]. 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 [19]. Concretely, Casper, Nehoran, and Sattath [18] 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 [18]. A fire state is simply a OSS signing key \(|sk\rangle\). The serial number is set to be the corresponding verification key \(pk\). We cannot directly clone \(|sk\rangle\), since that would violate OSS security. Instead, we ask the”cloner" to sample two public key-secret key pairs \((|sk_0\rangle, pk_0), (|sk_1\rangle pk_1)\) and subsequently obtain a signature \(\sigma\) by signing \(pk_0||pk_1\) using \(|sk\rangle\). The cloner outputs \(((pk_0, pk_1, \sigma),pk_0, |sk_0\rangle)\) and \(((pk_0, pk_1, \sigma), pk_1, |sk_1\rangle)\). 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(\lambda))\) clones, [18] 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 [18] shows that min entropy property must hold for any serial number ensuring correctness.

3 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.

3.1 Parameters↩︎

Let \(\lambda \in \mathbb{N}\) be the statistical security parameter. Recall that the OSS Construction \(52\) in Shmueli and Zhandry’s work [7] defines the following parameters in terms of \(\lambda\): \(n,r,k,s,d,\kappa, l\). The parameters \(n,r,k,s\) determine the sizes and dimensions of subspaces and cosets; \(l = \mathcal{O}(n)\) denotes the length of the signed message; and \(\kappa\), which is the size of PPRF key, determines the security level of the underlying pseudorandom function. For most of our work, we follow Shmueli and Zhandry’s recommendations in parameter instantiation, with one exception: while they recommend \(s = 16\lambda\), we use \(s = 2\lambda\). This choice is the smallest value satisfying the structural requirement [7] \(s' = s - (n-r-s) > 0\), as well as ensuring the conditions in the lemmata are satisfied. In [7], the constraint \(s \geq 16\lambda\) is employed to rule out all possible QPT attacks but \(s = 2\lambda\) is sufficient to rule out the most likely attacks described in Sec.5.

Following [7], we set

\[\begin{align} r = s\cdot(\lambda - 1) = 2\lambda(\lambda - 1), \quad n = r + \tfrac{3}{2}\cdot s = 2\lambda^2 + \lambda, \quad k = n, \end{align}\] and choose the PPRF key length \(\kappa\) such that for \(0<\delta<1\) \[\begin{align} \kappa&\geq (9 + 2\lambda(\lambda - 1) + \lambda^\delta + 2\lg(2\lambda^2+\lambda))^{1/\delta}. \end{align}\] 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 \(\kappa = |k_{\text{lin}}|\). The parameter \(s\) is the bloating factor of the dual subspace, expanding it by exactly \(s\) dimensions [7].

More discussion on the possible attacks we consider, security parameters, and how they are chosen can be found in Sec. 5.1

3.2 Cryptographic primitives↩︎

A pseudorandom function (PRF) is a deterministic algorithm that takes as input a key \(k\) from a key space \(\mathcal{K}\), an input \(x\) from an input space \(\mathcal{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\in 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.

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.

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 [10] builds a PPRF, \(\mathcal{F}: \{0,1\}^{\kappa}\times\{0,1\}^{r} \to\{0,1\}^{\kappa}\), from a length doubling PRG, \(G: \{0,1\}^\kappa \rightarrow \{0,1\}^{2\kappa}\). The output splits into two \(\kappa\)-bit strings, \[\begin{align} G(s) = \underbrace{G_0(s)}_{\kappa\text{ bits}} \, \| \, \underbrace{G_1(s)}_{\kappa\text{ bits}} \end{align}\] Thae PRF is defined as, \[\begin{align} (k,y) \stackrel{\mathcal{F}}{\mapsto} (G_{y_{-1}}(\cdots G_{y_1}(G_{y_0}(k))\cdots)) \end{align}\] The input \(y \in \{0,1\}^r\) determines a path of length \(r\) through the binary tree, with the leaves representing the PRF outputs.

Since the GGM construction is puncturable [32], the punctured key for a PPRF allows evaluation of the PRF tree at all points except a specific input \(y^*\). Let \(P_{y^*}\) be the path from \(\mathrm{root}\) to \(y^*\) and \(N_{y^*}\) be the set of all neighbouring nodes in \(P_{y^*}\). The punctured key is the set of values of all the nodes in \(N_{y^*}\). 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 6 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. 5.2.3 for more details.

3.3 Setup↩︎

Our setup is done at a higher level than [7]. A trusted third party samples a \(k_{\text{lin}}\in \{0,1\}^{\kappa}\) 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. 5.

3.4 KeyGen↩︎

(Tom’s comment: This reads like background rather than an intro to our key generation.) (Mia’s comment: I think we don’t need the red text as this had been described in Section A. the high-level structure.)

The non-collapsing, collision-resistant hash function used in OSS constructions (e.g., [6], [7], [9]) is a central building block in generating the quantum signing key. The hash function is obtained by truncating the output of a random permutation \(\Pi:\{0,1\}^n\to \{0,1\}^n\) to produce a hash value \(y=H(x)\). This value \(y\) is then fed into a random function \(F(y)\), whose output determines a hidden affine subspace \(C_y\). To produce the quantum secret key state, the oracle \(P\) first evaluates \(\Pi\) and then \(F\) in superposition. Measuring the truncated output register yields a uniformly random hash value \(y\), and applying the inverse oracle \(P^{-1}\) removes the auxiliary structure. As a result, the post-measurement state collapses to a uniform superposition over the affine subspace. This resulting state is the coset state associated with \(y\). The coset states are fundamental because they encode, in a quantum superposition, the hidden affine subspaces \(C_y\) defined by the random function \(F\). Hence, recovering or duplicating this structure requires solving a hard hidden-subspace problem, which, in turn, would violate the hash function’s non-collapsing collision resistance, giving OSS its unclonability and “one-shot” property. [7] introduced two constructions: the oracle model and the plain model. (Tom’s comment: one that’s (insert security properties) secure in the oracle model and a similar construction with (insert security properties) security in the plain model.) (Tom’s comment: Could we clarify this?) To achieve the randomness and security requirements, they introduce a new concept, the Permutable Pseudorandom Permutation, instead of using a random permutation, and utilize the Puncturable Pseudorandom Function to generate the coset state. Still, while working on concrete implementations for the oracles, we noticed that it’s possible to sample key pairs without performing the permutation. This is due to the fact that after creating the superposition of all inputs using \(n\) Hadamard gates, we obtain the state \(|+\rangle^{\otimes n}\), which is an eigenstate of any permutation. We understand that removing this permutation provides an efficient way to re-prepare any secret key state.

This could be avoided by using appropriate obfuscation, thus removing the resource costs necessary to implement the PRP.

Hence, in this work, our approach is a hybrid implementation that assumes a random permutation (Tom’s comment: Do we mean “fixes" a random perm?), applies the puncturable PRF, and estimates the resources needed to generate a quantum secret key and perform a signature.

As seen in the Workflow diagram 3, the key generation circuit factors as \(\mathrm{\small KeyGen} = H^{\otimes n+l}; F; \mathrm{\small Measure}\). The factor \(F\) is a puncturable PRF that relates public keys to a hidden coset space, encoded as an affine transformation (\(z\mapsto A_yz + b_y\)).

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 \(\mathrm{\small GGM.Lookup}\) and \(\mathrm{\small Graff}\), and describe their implementation in the sections that follow.

3.4.1 Implementing the GGM.Lookup↩︎

The GGM PPRF construction [10] creates a binary tree of keys by iterating a length-doubling PRG, \(G:\{0,1\}^{\kappa} \to \{0,1\}^{2\kappa}\), along any path \(p\in\{0,1\}^*\), in the pattern \[\begin{align} G(k) &= (k_0, k_1) \\ G(k_p) &= (k_{p||0}, k_{p||1}) \end{align}\] We call \(k\) the root key of the tree. The leaves define the value of the PPRF on a point \(x \in \{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.[33] 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, \(\mathrm{\small kLin}\), that writes \(k_{\text{lin}}\) into a register using CNOT gates. The children are pebbeled by the \(\mathrm{\small NextKey}\) query oracle, \(|p, k_p , 0^\kappa\rangle \xrightarrow{\mathrm{\small NextKey}} |p, k_p, k_q\rangle\). 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^{\kappa/2}, 0^{\kappa/2-1}1\rangle\), and use the point on the path to control the second qubit. This gives \(|0^{\kappa/2-2}y_i0, 0^{\kappa/2-2}y_i1\rangle\), which is then enciphered. Otherwise, (eg, when using the Simon cipher with \(\kappa=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.

The simplest reversible path traversal circuit caches every intermediate key. It uses \(\Theta(r)\) NextKey calls and \(\Theta(r\kappa)\) 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^\kappa\rangle\), \(|1\rangle\) denote the GGM root (\(k_{\text{lin}}\)), and successors denote the key value along the GGM path. The gadgets above in this shorthand become \[\begin{align} 0 &\xleftrightarrow{O} 1 \\ n, 0 &\xleftrightarrow{P} n, n+1 \\ \end{align}\] We use subscripts to precise relevant registers (eg, \(n,m,0 \xrightarrow{P_{0,2}} n,m,n+1\)) and omit them when obvious. The pebble operation with a fixed register also creates new single-register reversible operations, \(0 \xleftrightarrow{\mathrm{\small P}} v_i + 1\) where \(v_i\) 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 \(0^R \xleftrightarrow{} x, 0^{R-1}\) can reach? An adapted binary search works well. Use \(W^R_O\) to denote the optimal process on \(R\) registers with a circuit \(O\) that pebbles the root. Run \(W^{R-1}_O\) on the rightmost \(R-1\) registers to get \(0^R \xrightarrow{W} 0, x^*_{R-1}, 0^{R-2}\). Swap \(x_{R-1}\) into register zero, and run \(W^{R-1}_{P_0}\) on the rightmost \(R-1\) registers, with the zero pebble set to use \(P_0\). This gives \(x_{2(R-1)} , x_{R-1} , 0^{R-2}\) after swapping. The \(x_{R-1}, 0^{R-2}\) can be uncomputed by running \(W\) in reverse. That is \(W^R_O = W^{R-1}_O ; \text{SWAP} ; W^{R-1}_{P_{R-1}} ; \text{SWAP}; W^{R-1}_O{}^\dagger\) for \(R>1\) and \(W^1_O=O\). The \(R=3\) case shows the structure: \[\begin{align} \xrightarrow{\mathrm{\small Reset}} 0, 0, 0 \xrightarrow{O} 0, 0, 1 \xrightarrow{\mathrm{\small SWAP}}0, 1, 0 \xrightarrow{\mathrm{\small P}}0, 1, 2 \xrightarrow{\mathrm{\small SWAP}}0, 2, 1 \xrightarrow{O} 0, 2, 0 \xrightarrow{\mathrm{\small SWAP}}2, 0, 0 \xrightarrow{W} 2, 4, 0 \xrightarrow{\mathrm{\small SWAP}}4, 2, 0 \xrightarrow{W^\dagger} 4, 0, 0 \end{align}\]

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 = 2^R\). Iterating the process on the remaining free registers reaches a maximum depth of \(2^R-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 = \lceil \lg(r + 2) \rceil\) registers are required to reach that depth. Moreover, since each \(W\) splits into three subproblems with half the problem size, the algorithm must make \(\Theta(r^{\lg(3)})\) calls to NextKey.

We note that this approach is in essence Bennett’s simulation technique from [33] with \(m=2\).

3.4.2 Implementing the PRG↩︎

The GGM circuit builder works for any reversible implementation of a block cipher, \(|k, x\rangle \xrightarrow{\mathrm{\small Cipher}} |k, \mathrm{\small Cipher}_k (x)\rangle\). 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 [34] and Simon [35]. 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 \(\kappa\).

PRESENT [34] 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  [36].

SIMON [35] 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. [37] 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 1.

3.4.3 Uniform coset generation using Bruhat decomposition↩︎

Proceeding with the algorithmic workflow, the subsequent step involves generating the coset. As in the [7] construction, our implementation uses the PPRF \(F\) to sample a random coset \(C_y\) defined by a full-column rank matrix \(A_y\in\mathbb{Z}_2^{n\times (n-r)}\) and a random vector \(b_y\) \(\in\) \(\mathbb{Z}_2^n\). 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 \(k_y = \mathcal{F}(k_{\text{lin}}, 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(k_{\text{lin}}, y)\) is subsequently used in conjunction with Bruhat decomposition to generate a matrix-vector pair \((A_y, b_y)\), which defines a random coset.

\[\begin{align} F: \{0,1\}^{\kappa} \times \{0,1\}^{r} &\longrightarrow \{0,1\}^* \nonumber \\ (k_{\text{lin}}, y) &\xmapsto{\quad \mathcal{F} \quad} k_y = \mathcal{F}(k_{\text{lin}},y) \nonumber \\ &\xmapsto{\quad E \quad} E_{k_y}(\text{iv}) \parallel E_{k_y}(E_{k_y}(\text{iv})) \parallel \dots \end{align}\] where \(\text{iv}\) is the initialization vector of the block cipher. The columns of \(A_y\) span an \((n-r)\)-dimensional linear subspace \(\operatorname{Im}(A_y) = \{ A_y z : z\in\mathbb{Z}_2^{n-r}\}\). A coset \(C_y\) of \(\operatorname{Im}(A_y)\) is obtained by adding a vector \(b_y\) to every element of \(\operatorname{Im}(A_y)\), thereby shifting the entire subspace by \(b_y\). In our setting, \(C_y\) serves as the affine subspace associated with \(y\): \[\begin{align} C_y := b_y + \operatorname{Im}(A_y), \qquad \operatorname{Im}(A_y) = \{ A_y z : z\in\mathbb{Z}_2^{n-r}\}. \end{align}\]

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(k_{\text{lin}},y)\) using the Bruhat decomposition.

1. Sampling a random coset

   One can think of the coset \(C_y\) as an element of the affine Grassmannians \(\text{Graff}_{\mathbb{Z}_2}(n-r,n)\), the set of all \((n-r)\)-dimensional affine subspaces of \(\mathbb{Z}_2^n\), represented concretely by the pair \((A_y,b_y)\) where: \[\begin{align} \text{Graff}_{\mathbb{Z}_2}(n-r, n) := \{(\mathcal{L}, b) : \mathcal{L} \in \mathrm{Gr}(n-r,n)(\mathbb{Z}_2),\;b \in \mathbb{Z}_2^n\}. \end{align}\] The set of all \(n-r\)-dimensional subspaces of an \(n\)-dimensional vector space over a field \(\mathbb{Z}_2\), denoted by \(Gr(n-r,n)(\mathbb{Z}_2)\), is called the Grassmannian. The affine Grassmannian \(\text{Graff}_{\mathbb{Z}_2}(n-r,n)\) extends this set by allowing subspaces to be shifted by \(b_y \in \mathbb{Z}_2^n\). Hence, to sample a random coset \(C_y \in \text{Graff}_{\mathbb{Z}_2}(n-r,n)\), we first sample a random element \(\operatorname{Im}(A_y)\) in \(\mathrm{Gr}(n-r,n)(\mathbb{Z}_2)\), and sample a random vector \(b_y\).

   Note that any binary matrix \(A_y \in \mathbb{Z}_2^{\,n \times (n-r)}\) can always be written in the form \[\begin{align} A_y = P_y \begin{bmatrix} I_{n-r} \\ R_y \end{bmatrix} S_y \label{eq:general95form95ay} \end{align}\tag{1}\] for some matrices \(P_y \in \mathrm{GL}_n(\mathbb{Z}_2)\), \(S_y \in \mathrm{GL}_{n-r}(\mathbb{Z}_2)\), and \(R_y \in \mathbb{Z}_2^{\, r \times n-r}\). Its columns span a \((n-r)\)-dimensional subspace of the \(n\)-dimensional vector space over the field \(\mathbb{Z}_2\) (with \(r < n\)).

   Consider any invertible matrix \(P_y \in \mathrm{GL}_n(\mathbb{Z}_2)\) and a fixed \((n-r)\)-dimensional subspace \(\operatorname{Im}(A_y) \subseteq \mathbb{Z}_2^n\) represented by the columns of a full-column-rank matrix \(A_y\). Multiplying this matrix by \(P_y\) simply produces another matrix whose columns span a new \((n-r)\)-dimensional subspace \(P\operatorname{Im}(A_y)\). Moreover, every \((n-r)\)-dimensional subspace of \(\mathbb{Z}_2^n\) can be expressed in this way: for any such subspace \(\mathcal{L}'\), there exists an invertible matrix \(P_y\) for which \[\begin{align} P_y\operatorname{Im}(A_y) = \mathcal{L}'. \end{align}\] A convenient choice of reference subspace is the canonical one \[\begin{align} \mathbb{Z}_2^{\,n-r} := \mathrm{span}\{e_1, \dots, e_{n-r}\}, \end{align}\] and any other \((n-r)\)-dimensional subspace of \(\mathbb{Z}_2^n\) can be written as \(P_y \mathbb{Z}_2^{\,n-r}\) for some \(P_y \in \mathrm{GL}_n(\mathbb{Z}_2)\). Hence, multiplying the canonical matrix by different invertible matrices \(\mathrm{GL}_n(\mathbb{Z}_2)\) generates all such subspaces. This also shows that the specific matrices \(R\) and \(S\) appearing in the decomposition 1 are not important for sampling a random subspace. Thus, we may set \(R = 0\) and \(S = I_{n-r}\), yielding the simplified form \[\begin{align} A_y = P_y\begin{bmatrix} I_{n-r}\\[2pt] 0 \end{bmatrix}. \end{align}\]

   The problem of sampling a random linear subspace is now reduced to sampling a matrix \(P_y\in \mathrm{GL}_n(\mathbb{Z}_2)\). 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 to implement \(A_y^{-1}\) or \(A_y^{T}\) .

2. Bruhat Decomposition

   For \(\mathrm{GL}_n(\mathbb{Z}_2)\), let \(B\) be the subgroup of \(\mathrm{GL}_n(\mathbb{Z}_2)\) consisting of all upper triangular invertible matrices and \(S_n\) be the group of all permutation matrices. The Bruhat decomposition [38] then takes the form \[\begin{align} \mathrm{GL}_n(\mathbb{Z}_2) = \bigsqcup_{\pi \in S_n} B \, \pi \, B. \end{align}\] Thus every matrix \(P_y \in \mathrm{GL}_n(\mathbb{Z}_2)\) can be written as \[\begin{align} P_y = U_1 \, S_\pi \, U_2, \end{align}\] weith \(U_1, U_2 \in B\) and \(S_\pi\) a permutation matrix.

It is important to note that sampling the permutation \(\pi\) uniformly from \(S_n\) does not yield a uniformly distributed matrix \(P_y\). Because the size of the Bruhat cell \(B \pi B\) over \(\mathbb{Z}_2\) is proportional to \(2^{\text{inv}(\pi)}\), where \(\text{inv}(\pi)\) is the number of inversions in \(\pi\), the permutation must be sampled according to the Mallows distribution [39], [40] to account for this exponential difference in cell sizes. The sequence of digits \((L_n, \dots, L_1)\) in Algorithm 7 represents the Lehmer code of the permutation \(\pi\). 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 \(U_1\) 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 \(U_1\) and \(U_2\). 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 \(b_y\) can be implemented by CNOTs.

We require \(\Omega(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.

3.4.4 Generalization to multi-bit messages↩︎

This key generation module can easily be generalized to handle signatures of multi-bit messages [8], [9]. 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.

To achieve this, the original full-column rank matrix \(A_y \in \mathbb{Z}_2^{n \times (n-r)}\) is augmented into a larger block matrix \(\tilde{A}_y \in \mathbb{Z}_2^{(n+l) \times (l + n - r)}\), defined as:

\[\begin{align} \tilde{A}_y = \begin{bmatrix} I_l & 0 \\ B_y & A_y \end{bmatrix} \end{align}\]

where \(I_l\) is the \(l \times l\) identity matrix, and \(B_y \in \mathbb{Z}_2^{n \times l}\) is a rectangular matrix filled with random bits generated via the PPRF alongside the random bits required to implement \(A_y\). Similarly, the random translation vector \(b_y\) is expanded from \(n\) bits to an \((n+l)\)-bit string. We can partition this expanded vector into two distinct components: \(b_y = b_y^{(1)} \,||\, b_y^{(2)}\), where \(b_y^{(1)} \in \mathbb{Z}_2^l\) and \(b_y^{(2)} \in \mathbb{Z}_2^n\).

When the augmented affine subspace is evaluated on an input vector constructed by concatenating an \(l\)-bit string \(\omega\) and an \((n-r)\)-bit string \(z\) (represented as the column vector \([\omega, z]^T\)), the transformation yields: \[\begin{align} \tilde{A}_y \begin{bmatrix} \omega \\ z \end{bmatrix} + \begin{bmatrix} b_y^{(1)} \\ b_y^{(2)} \end{bmatrix} = \begin{bmatrix} I_l & 0 \\ B_y & A_y \end{bmatrix} \begin{bmatrix} \omega \\ z \end{bmatrix} + \begin{bmatrix} b_y^{(1)} \\ b_y^{(2)} \end{bmatrix} = \begin{bmatrix} \omega + b_y^{(1)} \\ B_y \omega + A_y z + b_y^{(2)} \end{bmatrix} \end{align}\] This outputs an \((n+l)\)-bit string where the first \(l\) bits cleanly encode the input \(\omega\) shifted by \(b_y^{(1)}\), and the remaining \(n\) bits cryptographically mix \(\omega\) and \(z\) through the matrices \(B_y\) and \(A_y\), shifted by \(b_y^{(2)}\).

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.

3.5 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 [7] 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 \[\begin{align} |y\rangle\otimes |sk_y\rangle, \end{align}\] where the private state \(|sk_y\rangle\) is an equal superposition over an affine coset of a full-rank binary matrix \(A_y\in\mathbb{Z}_2^{n\times (n-r)}\): \[\begin{align} |sk_y\rangle = \frac{1}{\sqrt{2^{(n-r)}}} \sum_{z\in\mathbb{Z}_2^{(n-r)}} |A_y z + b_y\rangle \end{align}\]

Here \(b_y\in\mathbb{Z}_2^n\) is a pseudorandom bit string which is a part of the KeyGen algorithm. Thus \(|sk_y\rangle\) is the uniform superposition over the coset \[\begin{align} C_y := b_y + \operatorname{Im}(A_y), \qquad \operatorname{Im}(A_y) = \{ A_y z : z\in\mathbb{Z}_2^{(n-r)}\}. \end{align}\]

3.5.1 Structure of the Coset Space↩︎

We show here that any coset \(C=b+\operatorname{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 = A z + b \in C\), the first bit is \[\begin{align} x_1 = (A z + b)_1 = A_1 z \;+\; b_1, \end{align}\] where \(A_1\) is the first row of \(A\). Define \[\begin{align} C_0 := \{ x\in C : x_1 = 0\}, \qquad C_1 := \{ x\in C : x_1 = 1\}. \end{align}\]

3.5.1.1 Degenerate case: \(A_1 = 0\).

If the first row of \(A\) is the zero vector, then \(A_1 z = 0\) for every \(z\), and therefore \[\begin{align} x_1 = b_1 \quad\text{for all } x\in C. \end{align}\] Which means, \[\begin{align} C_0 = C,\; C_1 = \varnothing \quad\text{or}\quad C_1 = C,\; C_0 = \varnothing. \end{align}\] In this case, the coset is constant with respect to its first bit.

3.5.1.2 Generic case:

\(A_1 \neq 0\). Then there exists an index \(j\) such that \(A_{1,j}=1\). For any \(z\in\mathbb{Z}_2^{(n-r)}\), define \(z'\in\mathbb{Z}_2^{(n-r)}\) by flipping the \(j\)-th bit and keeping all other coordinates fixed: \[\begin{align} z'_j = \lnot z_j, \qquad z'_i = z_i \;\text{for all } i\neq j. \end{align}\] Since \(A_{1,j}=1\), we compute \[\begin{align} A_1 z' = \sum_{i\neq j} A_{1,i} z_i \;+\; A_{1,j}\,\lnot z_j = \sum_{i\neq j} A_{1,i} z_i \;+\; \lnot z_j. \end{align}\] Using \(\lnot z_j = z_j + 1\), this becomes \[\begin{align} A_1 z' = \sum_{i\neq j} A_{1,i} z_i \;+\; z_j \;+\; 1 = A_1 z \;+\; 1. \end{align}\] Thus \(A_1 z'\) always evaluates to the opposite value of \(A_1 z\), showing that a nonzero linear form on \(\mathbb{Z}_2^{(n-r)}\) is necessarily balanced. So this proves that every affine coset \(C=b+\operatorname{Im}(A)\) satisfies exactly one of the following: \[\begin{align} \text{Either x_1 is constant on C, or C splits evenly into C_0 and C_1.} \end{align}\] In all nondegenerate constructions (where \(A_1\neq 0\)), the coset is perfectly balanced.

3.5.2 Single-Bit Signing↩︎

For a fixed public key \(y\), write the corresponding coset \[\begin{align} C_y = b_y + \operatorname{Im}(A_y) \subseteq \mathbb{Z}_2^n. \end{align}\] Assume we are in the generic case where the first row of \(A_y\) is nonzero, so \(C_y\) splits evenly according to the first coordinate: \[\begin{align} C_{y,0} := \{ x\in C_y : x_1 = 0 \}, \qquad C_{y,1} := \{ x\in C_y : x_1 = 1 \}, \end{align}\] with \[\begin{align} |C_{y,0}| = |C_{y,1}| = 2^{(n-r)-1}. \end{align}\] We define the two normalized “half-coset” states \[\begin{align} |sk_0\rangle &:= \frac{1}{\sqrt{2^{(n-r)-1}}} |0\rangle \otimes \sum_{x| (0,x)\in C_{y,0}} |x\rangle, \\ |sk_1\rangle &:= \frac{1}{\sqrt{2^{(n-r)-1}}} |1\rangle \otimes \sum_{x| (1,x)\in C_{y,1}} |x\rangle. \end{align}\] So that the full coset state can be written as \[\begin{align} |sk_y\rangle = \frac{1}{\sqrt{2^{(n-r)}}} \sum_{x\in C_y} |x\rangle = \frac{1}{\sqrt{2}}\bigl( |sk_0\rangle + |sk_1\rangle \bigr). \end{align}\] Here, we write \(|sk\rangle := |sk_y\rangle\) in what follows.

Given a one-bit message \(m\in\{0,1\}\), the signer uses the first qubit of \(|sk\rangle\) as follows:

1. Measure the first qubit of \(|sk\rangle\) in the computational basis, obtaining an outcome \(c\in\{0,1\}\). The post-measurement state collapses to \(|sk_c\rangle\).

2. If \(c = m\), the signer measures the remaining \(n-1\) qubits in the computational basis. The resulting classical string \(x \in C_{y,m}\) serves as the signature.

3. If \(c \neq m\), apply the logical \(X\) operator (\(X_L\)) to swap the half-coset states, transforming the state to \(|sk_m\rangle\). Measure the remaining qubits to obtain the signature \(x \in C_{y,m}\).

In all cases, the final classical output lies in the desired half-coset \(C_{y,m}\), i.e.its first bit equals the message bit \(m\).

3.5.2.1 Logical \(X\) on the Coset Qubit

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 \(|sk_0\rangle\) and \(|sk_1\rangle\) span a two-dimensional logical qubit. We define the logical \(X\) operator on this encoded qubit by \[\begin{align} X_L := |sk_0\rangle\!\langle sk_1| + |sk_1\rangle\!\langle sk_0|. \end{align}\] By construction, \[\begin{align} X_L |sk_0\rangle = |sk_1\rangle, \qquad X_L |sk_1\rangle = |sk_0\rangle. \end{align}\]

It is convenient to introduce the symmetric and antisymmetric combinations \[\begin{align} |sk\rangle := \frac{1}{\sqrt{2}}\bigl( |sk_0\rangle + |sk_1\rangle \bigr), \qquad |sk'\rangle := \frac{1}{\sqrt{2}}\bigl( |sk_0\rangle - |sk_1\rangle \bigr), \end{align}\] which form an orthonormal basis of the same logical subspace. We now compute the action of \(X_L\) on these states: \[\begin{align} X_L |sk\rangle &= \frac{1}{\sqrt{2}} \bigl( X_L |sk_0\rangle + X_L |sk_1\rangle \bigr) = \frac{1}{\sqrt{2}} \bigl( |sk_1\rangle + |sk_0\rangle \bigr) = |sk\rangle,\\[4pt] X_L |sk'\rangle &= \frac{1}{\sqrt{2}} \bigl( X_L |sk_0\rangle - X_L |sk_1\rangle \bigr) = \frac{1}{\sqrt{2}} \bigl( |sk_1\rangle - |sk_0\rangle \bigr) = -\,|sk'\rangle. \end{align}\] Thus \(|sk\rangle\) and \(|sk'\rangle\) are eigenstates of \(X_L\) with eigenvalues \(+1\) and \(-1\), respectively: \[\begin{align} X_L |sk\rangle = +\,|sk\rangle, \qquad X_L |sk'\rangle = -\,|sk'\rangle. \end{align}\] In this basis \(\{|sk\rangle,|sk'\rangle\}\), the logical \(X_L\) plays the role of a Pauli-\(Z\) operator, while in the basis \(\{|sk_0\rangle,|sk_1\rangle\}\) it acts as a standard Pauli-\(X\) that swaps the two half-coset states.

3.5.2.2 Logical \(X\) from Hadamards and a Phase on \(\operatorname{Im}(A_y)^\perp\)

The two states \[\begin{align} |sk\rangle=\frac{|sk_0\rangle+|sk_1\rangle}{\sqrt{2}},\qquad |sk'\rangle=\frac{|sk_0\rangle-|sk_1\rangle}{\sqrt{2}} \end{align}\] form an orthonormal basis for the two-dimensional coset subspace associated with \(C_y\). 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 \(A_y\) of full column rank, \[\begin{align} H^{\otimes n} |sk\rangle &= \frac{1}{\sqrt{2^{n-r}}}\sum_{z \in \{0,1\}^{n-r}} H^{\otimes n} |A_y z + b_y\rangle \\ &= \frac{1}{\sqrt{2^{n-r}}}\sum_{z \in \{0,1\}^{n-r}} \frac{1}{\sqrt{2^n}}\sum_{\omega\in \{0,1\}^{n}} (-1)^{\omega . (A_y z + b_y)} |\omega\rangle \\ &= \frac{1}{\sqrt{2^{n-r}}} \frac{1}{\sqrt{2^n}} \sum_{\omega\in \{0,1\}^{n}} (-1)^{\omega.b_y} \left(\sum_{z \in \{0,1\}^{n-r}} (-1)^{(A_y^{T}\omega).z}\right) |\omega\rangle \\ &= \frac{1}{\sqrt{2^r}} \sum_{\omega\in\operatorname{Im}(A_y)^\perp} (-1)^{\omega\cdot b_y}\,|\omega\rangle, \end{align}\] where \[\begin{align} \operatorname{Im}(A_y)^\perp := \{\omega\in\mathbb{Z}_2^n : A_y^T\omega = 0\} \end{align}\] is the orthogonal complement of the column space of \(A_y\). Thus \(H^{\otimes n}|sk\rangle\) has support exactly on \(\operatorname{Im}(A_y)^\perp\).

We now analyse the Hadamard action on the other state, \[\begin{align} |sk'\rangle := \frac{1}{\sqrt{2}}\left(|sk_0\rangle - |sk_1\rangle\right). \end{align}\] Note that \(|sk'\rangle\) is a uniform superposition over the full coset \(C_y = b_y + \operatorname{Im}(A_y)\), but with a relative phase of \(-1\) applied to elements where the first bit is \(1\). Let \(e_1 = (1,0, \dots, 0)\) be the unit vector bit string corresponding to the first coordinate. For any vector \(x = A_y z + b_y \in C_y\), its first bit is exactly the dot product \(e_1 \cdot (A_y z + b_y)\). Thus, we can write \(|sk'\rangle\) algebraically as: \[\begin{align} |sk'\rangle = \frac{1}{\sqrt{2^{n-r}}} \sum_{z \in \{0,1\}^{n-r}} (-1)^{e_1 \cdot (A_y z + b_y)} |A_y z + b_y\rangle. \end{align}\]

Applying the global Hadamard transform \(H^{\otimes n}\) gives: \[\begin{align} H^{\otimes n} |sk'\rangle &= \frac{1}{\sqrt{2^{n-r}}} \sum_{z \in \{0,1\}^{n-r}} (-1)^{e_1 \cdot (A_y z + b_y)} H^{\otimes n} |A_y z + b_y\rangle \\ &= \frac{1}{\sqrt{2^{n-r}}} \frac{1}{\sqrt{2^n}} \sum_{z \in \{0,1\}^{n-r}} \sum_{\omega \in \{0,1\}^n} (-1)^{e_1 \cdot (A_y z + b_y)} (-1)^{\omega \cdot (A_y z + b_y)} |\omega\rangle. \end{align}\]

Since we are working on \(\mathbb{Z}_2\), we can combine the phases: \[\begin{align} H^{\otimes n} |sk'\rangle &= \frac{1}{\sqrt{2^{n-r}}} \frac{1}{\sqrt{2^n}} \sum_{\omega \in \{0,1\}^n} \sum_{z \in \{0,1\}^{n-r}} (-1)^{(\omega + e_1) \cdot (A_y z + b_y)} |\omega\rangle \\ &= \frac{1}{\sqrt{2^{n-r}}} \frac{1}{\sqrt{2^n}} \sum_{\omega \in \{0,1\}^n} (-1)^{(\omega + e_1) \cdot b_y} \left( \sum_{z \in \{0,1\}^{n-r}} (-1)^{(A_y^T (\omega + e_1)) \cdot z} \right) |\omega\rangle. \end{align}\]

The inner sum over \(z\) evaluates to \(2^{n-r}\) if \(A_y^T (\omega + e_1) = 0\), and \(0\) otherwise. This condition is equivalent to requiring that \(\omega + e_1 \in \operatorname{Im}(A_y)^\perp\). Shifting \(e_1\) to the other side, we define the support slice \(S\) as: \[\begin{align} S := \operatorname{Im}(A_y)^\perp + e_1 = \{ \omega \in \mathbb{Z}_2^n : \omega + e_1 \in \operatorname{Im}(A_y)^\perp \}. \end{align}\] Thus, the state simplifies to: \[\begin{align} H^{\otimes n} |sk'\rangle = \frac{1}{\sqrt{2^r}} \sum_{\omega \in S} (-1)^{(\omega + e_1) \cdot b_y} |\omega\rangle. \end{align}\]

Because we assumed the generic case where the first row of \(A_y\) is nonzero, the unit vector \(e_1\) is not orthogonal to the column space of \(A_y\), meaning \(e_1 \notin \operatorname{Im}(A_y)^\perp\). Consequently, the shifted subspace \(S\) and the original subspace \(\operatorname{Im}(A_y)^\perp\) are completely disjoint: \[\begin{align} \operatorname{Im}(A_y)^\perp \cap S = \varnothing. \end{align}\]

Hence the Fourier supports of \(|sk\rangle\) and \(|sk'\rangle\) are completely disjoint. Now we can define a diagonal operator such that \[\begin{align} D = \sum_{\omega\in\mathbb{Z}_2^n} \phi(\omega)\,|\omega\rangle\!\langle\omega|, \qquad \phi(\omega)= \begin{cases} 1,& \text{if }A_y^T\omega=0,\\[4pt] -1,& \text{otherwise}. \end{cases} \end{align}\] \(D\) can also be written as following,

\[\begin{align} D = e^{i\pi \sum\limits_{\omega\notin \operatorname{Im}(A_y)^\perp} |\omega\rangle\langle\omega|} \end{align}\]

Combining all these we get

\[\begin{align} X_L = H^{\otimes n} D H^{\otimes n} \end{align}\]

3.5.3 Multi-bit Signing Using Iterative Measurements↩︎

The one-bit signing algorithm generalizes to \(l \sim O(\mathrm{poly}(\lambda))\) bits by expanding the transformation matrix. We define the augmented binary matrix \(\tilde{A}_y \in \mathbb{Z}_2^{(n+l) \times (n+l-r)}\) as follows:

\[\begin{align} \tilde{A}_y = \begin{pmatrix} I_l & 0 \\ B_y & A_y \end{pmatrix} \end{align}\]

where \(B_y \in \mathbb{Z}_2^{n \times l}\) is a matrix of random bits and \(A_y \in \mathbb{Z}_2^{n \times (n-r)}\). This matrix acts on a combined vector \((w \parallel z) \in \mathbb{Z}_2^{l + (n-r)}\). Given a random shift vector \(b_y = (b_y^{(l)} \parallel b_y^{(n)}) \in \mathbb{Z}_2^{n+l}\), the state preparation follows the affine transformation:

\[\begin{align} |\psi\rangle = \frac{1}{\sqrt{2^{n+l-r}}} \sum_{w \in \mathbb{Z}_2^l} \sum_{z \in \mathbb{Z}_2^{n-r}} |w + b_y^{(l)}\rangle |B_y w + A_y z + b_y^{(n)}\rangle \end{align}\]

3.5.3.1 The Iterative Measurement Procedure

To sign an \(l\)-bit message \(m \in \mathbb{Z}_2^l\), the signer measures the first \(l\) qubits sequentially. Let \(p_i\) denote the measurement outcome of the \(i\)-th qubit.

• Comparison: If \(p_i = m_i\), the signer proceeds to measure the \((i+1)\)-th qubit.

• Correction: If \(p_i \neq m_i\), 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 \(X_{L,i}\) before proceeding to the next bit.

The flip gate is defined as: \[\begin{align} \label{eq:flip} X_{L,i} = H^{\otimes (n+l)} D_i H^{\otimes (n+l)} \end{align}\tag{2}\]

As an example let’s discuss what happens when we measure the first qubit and get the wrong measurement, \(p_1 \neq m_1\).

The measurement projects the state such that the first bit is fixed to \(p_1\). Since the first register is \(|w + b_y^{(l)}\rangle\), this restricts the summation to values of \(w\) where \(w_1 + (b_y^{(l)})_1 = p_1\). Let \(w_{>1}\) denote the remaining \(l-1\) free bits of \(w\). The post-measurement state becomes:

\[\begin{align} |\psi_{\text{bad}}\rangle = \frac{1}{\sqrt{2^{n+l-r-1}}} \sum_{\substack{w \in \mathbb{Z}_2^l \\ w_1 = p_1 + (b_y^{(l)})_1}} \sum_{z \in \mathbb{Z}_2^{n-r}} |w + b_y^{(l)}\rangle |B_y w + A_y z + b_y^{(n)}\rangle \end{align}\]

The signer applies \(H^{\otimes (n+l)}\) to move to the dual space, introducing dual variables \(u^{(l)} \in \mathbb{Z}_2^l\) and \(u^{(n)} \in \mathbb{Z}_2^n\):

\[\begin{align} H^{\otimes (n+l)} |\psi_{\text{bad}}\rangle = \frac{1}{\sqrt{2^{n+l-r-1}} \sqrt{2^{n+l}}} \sum_{w_1 =p_1} \sum_{w_{>1}} \sum_{z} \sum_{u^{(l)}, u^{(n)}} (-1)^{\Phi} |u^{(l)}\rangle |u^{(n)}\rangle \end{align}\]

where the phase \(\Phi\) is given by the inner products:

\[\begin{align} \Phi = u^{(l)} \cdot (w + b_y^{(l)}) + u^{(n)} \cdot (B_y w + A_y z + b_y^{(n)}) \end{align}\]

We rearrange the phase to group the terms by the summation variables \(w\) and \(z\):

\[\begin{align} \Phi &= \underbrace{(A_y^T u^{(n)}) \cdot z}_{\text{forces } A_y^T u^{(n)} = 0} + \underbrace{(u^{(l)} + B_y^T u^{(n)}) \cdot w}_{\text{splits into } w_1 \text{ and } w_{>1}} \nonumber \\ &\quad + \underbrace{u^{(l)} \cdot b_y^{(l)} + u^{(n)} \cdot b_y^{(n)}}_{\text{constant phase}} \end{align}\]

The sums over \(z\) and the free variables \(w_{>1}\) act as interference filters:

• Summing over \(z \in \mathbb{Z}_2^{n-r}\) evaluates to \(0\) unless \(A_y^T u^{(n)} = 0\).

• Summing over the \(l-1\) free bits of \(w_{>1}\) evaluates to \(0\) unless \((u^{(l)} + B_y^T u^{(n)})_j = 0\) for all \(j \in \{2, \dots, l\}\).

Crucially, because \(w_1\) was fixed by the measurement, there is no sum over \(w_1\). Therefore, the first component of the message constraint is relaxed.

The dual state has support only where those constraints are met. For the unconstrained bit, let \(v_1 = u^{(l)}_1 + (B_y^T u^{(n)})_1 \in \{0, 1\}\). The phase contribution from the fixed \(w_1\) bit becomes \((-1)^{v_1(p_1 + (b_y^{(l)})_1)}\). The state simplifies to:

\[\begin{align} H^{\otimes (n+l)} |\psi_{\text{bad}}\rangle \propto \sum_{\substack{u^{(l)}, u^{(n)} \\ A_y^T u^{(n)} = 0 \\ \forall j \neq 1, \; u^{(l)}_j = (B_y^T u^{(n)})_j}} (-1)^{v_1(p_1 + (b_y^{(l)})_1) + \dots} |u^{(l)}\rangle |u^{(n)}\rangle \end{align}\]

Because \(v_1 = u^{(l)}_1 + (B_y^T u^{(n)})_1\) is free to take values \(0\) or \(1\), the dual state splits evenly across these two values. Applying the oracle \(D_1\) with the phase \((-1)^{u^{(l)}_1 + (B_y^T u^{(n)})_1}\) directly toggles the sign between these two halves, which perfectly corresponds to swapping the primal state from \(p_1\) to \(\lnot p_1\) (the correct message bit \(m_1\)) once the Hadamards are applied again.

3.5.3.2 The Dual-Space Phase Oracle \(D_i\)

The operator \(D_i\) in Eq. 2 is defined in the Hadamard (dual) basis. Let \(u = (u^{(l)} \parallel u^{(n)})\) be the dual variables. Before any measurement, the state satisfies the constraint \(u^{(l)}_j + (B_y^T u^{(n)})_j = 0\) for all \(j \in \{1, \dots, l\}\).

If the measurement of the \(i\)-th qubit yields an incorrect outcome \(p_i \neq m_i\), the state collapses and the \(i\)-th primal variable is fixed. This relaxes the corresponding \(i\)-th dual constraint. Consequently, the term \(u^{(l)}_i + (B_y^T u^{(n)})_i\) takes values \(0\) and \(1\) with equal probability across the superposition.

We define the phase oracle \(D_i\) to act on this bit: \[\begin{align} D_i |u^{(l)}\rangle |u^{(n)}\rangle = (-1)^{u^{(l)}_i + (B_y^T u^{(n)})_i} |u^{(l)}\rangle |u^{(n)}\rangle \end{align}\]

Applying \(D_i\) introduces a \(-1\) phase to the subspace where \(u^{(l)}_i + (B_y^T 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 \(p_i\) to \(m_i\). The state of all other coordinates \(j \neq i\) remains unchanged.

3.5.3.3 Signature Extraction

Because the localized flip operators \(X_{L,i} = H^{\otimes (n+l-i)} D_i H^{\otimes (n+l-i)}\) commute with the underlying subspace constraints and act as the identity on the logical subspaces of \(j \neq 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 \in \mathbb{Z}_2^l\), 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 that \(w + b_y^{(l)} = m\), which implies \(w = m + b_y^{(l)}\).

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 \in \mathbb{Z}_2^{n-r}\):

\[\begin{align} |\psi_{\text{final}}^{(n)}\rangle = \frac{1}{\sqrt{2^{n-r}}} \sum_{z \in \mathbb{Z}_2^{n-r}} |B_y (m + b_y^{(l)}) + A_y z + b_y^{(n)}\rangle \end{align}\]

The signer then measures these remaining \(n\) qubits in the computational basis. The resulting bitstring \(\sigma \in \mathbb{Z}_2^n\) must take the form \(\sigma = B_y (m + b_y^{(l)}) + A_y z + b_y^{(n)}\) for some \(z\). Rearranging this equation yields the classical verification condition:

\[\begin{align} \sigma + b_y^{(n)} + B_y(m + b_y^{(l)}) = A_y z \in \operatorname{Im}(A_y) \end{align}\]

This confirms that the measured signature \(\sigma\) is valid and consistent with both the message \(m\) and the public key \(y\).

3.5.4 Multi-bit Signing Using Global Measurement and Translation↩︎

To sign an \(l\)-bit message \(m \in \mathbb{Z}_2^l\) using a global approach, the signer performs a simultaneous computational basis measurement of the first \(l\) qubits of the state \(|\psi\rangle\).

3.5.4.1 Global Correction Procedure

Let \(p\in \mathbb{Z}_2^l\) denote the observed \(l\)-bit measurement outcome. This measurement projects the first register into the state \(|p\rangle\), collapsing the remaining unmeasured qubits into the corresponding valid signature subspace for \(p\). If \(p \neq m\), the signer applies a global translation operator \(X_L\) 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: \[\begin{align} X_L = H^{\otimes (n+l)} D_{p \to m} H^{\otimes (n+l)} \end{align}\]

3.5.4.2 Global Dual Phase Oracle

The oracle \(D_{p \to 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:

\[\begin{align} D_{p \to m} |u^{(l)}\rangle |u^{(n)}\rangle = (-1)^{(u^{(l)} + B_y^T u^{(n)}) \cdot d} |u^{(l)}\rangle |u^{(n)}\rangle \end{align}\]

Expanding the phase term yields \(u^{(l)} \cdot d + u^{(n)} \cdot B_y 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 \(B_y d\), satisfying the affine structure of the augmented matrix \(\tilde{A}_y\).

To verify the global translation, we trace the state evolution through the application of \(X_L\).

1. Post-Measurement State: When the first register is measured as \(p \in \mathbb{Z}_2^l\), the internal variable \(w\) collapses such that \(w + b_y^{(l)} = p\), which implies \(w = p + b_y^{(l)}\). The normalized post-measurement state becomes a superposition over the free variables \(z \in \mathbb{Z}_2^{n-r}\): \[\begin{align} |\psi_{\text{post}}\rangle = \frac{1}{\sqrt{2^{n-r}}} \sum_{z \in \mathbb{Z}_2^{n-r}} |p\rangle |B_y (p + b_y^{(l)}) + A_y z + b_y^{(n)}\rangle \end{align}\]

2. First Hadamard Transform: Applying \(H^{\otimes (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 \(A_y^T u^{(n)} = 0\): \[\begin{align} |\psi_{\text{dual}}\rangle \propto \sum_{\substack{u^{(l)} \in \mathbb{Z}_2^l, \; u^{(n)} \in \mathbb{Z}_2^n \\ A_y^T u^{(n)} = 0}} (-1)^{\Phi_{\text{old}}} |u^{(l)}\rangle |u^{(n)}\rangle \end{align}\] where the initial dual phase is: \[\begin{align} \Phi_{\text{old}} = u^{(l)} \cdot p + u^{(n)} \cdot \bigl(B_y (p + b_y^{(l)}) + b_y^{(n)}\bigr) \end{align}\]

3. Applying the Oracle \(D_{p \to m}\): The oracle applies the phase shift \((-1)^{(u^{(l)} + B_y^T u^{(n)}) \cdot d}\), where \(d = p + m\). Using the property \((B_y^T u^{(n)}) \cdot d = u^{(n)} \cdot B_y d\), the new phase \(\Phi_{\text{new}}\) becomes: \[\begin{align} \Phi_{\text{new}} &= \Phi_{\text{old}} + u^{(l)} \cdot d + u^{(n)} \cdot B_y d \nonumber \\ &= u^{(l)} \cdot (p + d) + u^{(n)} \cdot \bigl(B_y (p + d) + B_y b_y^{(l)} + b_y^{(n)}\bigr) \end{align}\] Since \(d = p + m\), we have \(p + d = m\). Substituting this yields: \[\begin{align} \Phi_{\text{new}} = u^{(l)} \cdot m + u^{(n)} \cdot \bigl(B_y (m + b_y^{(l)}) + b_y^{(n)}\bigr) \end{align}\]

4. Second Hadamard Transform: The phase \(\Phi_{\text{new}}\) perfectly matches the dual-space representation of a state localized at \(m\) in the first register and affine-shifted by \(B_y(m + b_y^{(l)}) + b_y^{(n)}\) in the second register. Applying the final \(H^{\otimes (n+l)}\) returns the state to the primal basis: \[\begin{align} X_L |\psi_{\text{post}}\rangle = \frac{1}{\sqrt{2^{n-r}}} \sum_{z \in \mathbb{Z}_2^{n-r}} |m\rangle |B_y (m + b_y^{(l)}) + A_y z + b_y^{(n)}\rangle \end{align}\]

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\).

3.5.4.3 Complexity and Success

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 \(X_L\) 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 \(\sigma\), completing the protocol.

3.6 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 \(\sigma\) 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 \(k_{\text{lin}}\), the verifier performs a classical GGM tree search to resolve the corresponding leaf key.

2. Graff Inversion (\(\tilde{\boldsymbol{Graff}}\)): Using the derived leaf key, the verifier reconstructs the necessary coset parameters (\(P^{-1}_y\), \(B_y\), \(b_y\)). The verifier then computes the pre-image coordinate vector \(z\) using the message \(m\) and the signature component \(\tau\) via the following matrix computation: \[z = P_y^{-1} \cdot \left( B_y \cdot\left( m+b_y^{(l)}\right) + \tau + b_y^{(n)} \right)\] The inverse matrix \(P^{-1}_y\) 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 \(z_{n-r \dots n} \overset{?}{=} 0^{\otimes r}\).

   • Message Bit Check: The verifier ensures that the first \(l\) bits of the signature \(\sigma\) exactly match the signed message \(m\), confirming that \(\sigma_{1 \dots l} \overset{?}{=} m\).

4 Logical resources↩︎

4.1 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 \(\#Q_{\mathrm{\small OSS}} = r + n + \#Q_\mathrm{\small GGM.Lookup} + \#Q_\mathrm{\small Graff}\); however, due to the sequential nature of the circuits, there are some gestalt savings available.

We calculated above that Graff requires \(\text{bk}+n+1\) qubits. We also know that GGM.Lookup keeps checkpoints in only \(\lceil-\lg(1 - 2^{-R}(r+1))\rceil\) of its \(R := \lceil \lg(r+2) \rceil\) key registers. This leaves \(f = R - \lceil-\lg(1 - 2^{-R}(r+1))\rceil\) free key registers that can be repurposed to satisfy the Graff requirements. Moreover, GGM.Lookup adds an additional \(2\text{bk}\) qubits when run with small keys. Let \(Q_{\text{add}}\) denote the extra qubit overhead required when these repurposed free registers are insufficient to cover the Graff requirements, defined as: \(\varepsilon_{\text{add}} = \max(\text{bk}+n+1 - f - \varepsilon_{\text{small keys}}, 0)\).

Tying this all together gives the total logical qubit count: \[\label{eq:logical95qubits} \#Q_\mathrm{\small OSS} = r + n + R\kappa + \varepsilon_{\text{add}}\tag{3}\]

The first nine configurations are evaluated and tabulated in Table 2.

4.2 Logical gates↩︎

4.2.1 Key Generation↩︎

As stated above, GGM.Lookup has NextKey step complexity \(\Theta(r^{\lg(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 ¿tbl:tab:graff95gc?. 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.

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 3. We note that the \(\lambda=9\) circuit has a higher total gate count than the \(\lambda=10\) circuit; this is because \(\lambda=9\) runs a small key GGM.Lookup.

4.2.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 \(D_{p\rightarrow m}\). And we use Gr* to denote the circuit that applies the transpose of the linear part of \(\mathrm{\small Graff}\). An Equivocate circuit requires, \[\begin{align} \lVert\mathrm{\small Equivocate}\rVert_{\text{Gates}} = 2\lVert\mathrm{\small GGM.Lookup}\rVert_{\text{Gates}} + 2\lVert\mathrm{\small Gr*}\rVert_{\text{Gates}} + 2n\mathrm{\small H} + 2(n-r)\mathrm{\small X} + 2\mathrm{\small C}_{n-r}\mathrm{\small X} + \mathrm{\small Z} \end{align}\]

The \(C_jX\) gate can further be decomposed to \(2j-3\) CCX and \(2j-6\) X gates and a clean ancilla qubit [41]. The signing routine requires an equivocation half the time, giving an expected gate count: \[\begin{align} \mathbf{E} \lVert\mathrm{\small Sign}\rVert_{\text{Gates}} = n\mathrm{\small Measure} + \lVert\mathrm{\small Equivocate}\rVert_{\text{Gates}}/2 \end{align}\]

4.3 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. 3 to arrive at, \[\#Q = n+2l + r+\kappa\lceil\lg(r+2)\rceil \label{eq:LogicalQubitsMultiBit}\tag{4}\]

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.

• Graff: We need \(nl\) extra random bits to perform the action of \(B_y\). This requires \(\lceil \frac{nl}{bk}\rceil\) 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\)

5 Concrete security↩︎

5.1 Parameter choice and discussion on possible attacks↩︎

Let \(\lambda \in \mathbb{N}\) be the statistical security parameter. Recall that the OSS Construction \(52\) in Shmueli and Zhandry’s work [7] defines the following parameters in terms of \(\lambda\): \(n,r,k,s,d,\kappa\). The parameters \(n,r,k,s\) determine the sizes and dimensions of subspaces and cosets while \(\kappa\) 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 \(\kappa\) 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 [7] use \(\lambda\) 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 \((\mathrm{\small KeyGen}, \mathrm{\small Sign}, \mathrm{\small 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 \(\kappa\) 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 \in \{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\|0^r)\). The probability of finding such a valid \(u\) becomes high after trying \(O(\frac{2^{n}}{2^{n-r}}) = O(2^r)\) inputs.

  • In the quantum case, the adversary can prepare a superposition of all \(n\)-bit strings together with the known public key as follows: \(\sum_{x\in\{0,1\}^n}|x\rangle|y\rangle\). Using the quantisation of the classical verification circuit, the adversary can run Grover’s algorithm to find a valid signature in approximately \(O(2^{r/2})\) steps.

  Therefore, \(r\) must be scaled sufficiently large with the security parameter \(\lambda\) so that both attack complexities, \(O(2^r)\) classically and \(O(2^{r/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.

• \(\kappa\): controls the security of the underlying pseudorandom function. If \(\kappa\) is small, a quantum adversary can recover the PRF key \(k_{\text{lin}}\) using Grover search in \(O(2^{\kappa/2})\) oracle queries. The knowledge of \(k_{\text{lin}}\) allows the adversary to reconstruct the coset description \((A_y, b_y)\) 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 \(\kappa\). Assume that all cryptographic building blocks are subexponentially secure for a subexponential (in \(\lambda\)) function \(f(\lambda) = 2^{\lambda^{\delta}}\) with \(0<\delta<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 \(\kappa\), and for the total number of cosets \(2^r\)—which is also the number of possible hash digests \(y\)—the Bloating the Dual technique ensures that each coset \(C_y\) is embedded into a superspace \(T_y\) with \(C_y\subseteq T_y \subseteq \mathbb{Z}^k_2\). Under this construction, the value of \(\kappa\) is derived using the bound given in [7] guarantee that an adversary \(\mathcal{A}\) cannot tamper with the obfuscated circuit associated with these superspaces in order to exploit the collisions of the underlying hash function: \[\begin{align} \frac{2^r \cdot \frac{k^2}{\epsilon}}{f(\kappa)} &\leq \frac{1}{512} \\ \kappa&\geq (9 + 2\lambda(\lambda - 1) + \lambda^\delta + 2\lg(2\lambda^2+\lambda))^{1/\delta} \label{secineq} \end{align}\tag{5}\]

Appropriate values of \(\kappa\) for varying \(\lambda\) can be found in Table 2.

5.2 Obfuscation↩︎

5.2.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 [20]; Goldwasser and Rothblum [42] 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. [43], 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 \(s^{3.64}\), and Ananth et al. [44] analyze a line of constructions whose obfuscation size was \(O(s^{10.92})\) under a quadratic-cost assumption before being improved to \(O(s^5)\). To overcome the inherent restrictions and conversion overheads of formula-based obfuscation, subsequent works bootstrapped iO to more general computational models. Bitansky and Vaikuntanathan [45] showed how to obtain iO from sufficiently succinct functional encryption with obfuscation size \(2|C|+\mathrm{poly}(\lambda,d,n)\) for any circuit \(C\), where \(\lambda\) is the security parameter, \(d\) is circuit depth and \(n\) is input length, while Ananth, Jain, and Sahai [46] obtained bounded-input (by \(L\)) iO with size \(2|M|+\mathrm{poly}(\lambda, L)\) for any Turing machine \(M\). A major conceptual milestone was then achieved by Jain, Lin, and Sahai [47], 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. [48] simplified the assumption set by removing the need for polynomial-stretch \(\mathsf{NC}^0\) pseudorandom generators.

More recent work has improved efficiency in structured settings instead of merely proving existence. Jain and Jin [49] removed the exponential loss in the input length whenever functional equivalence admits short propositional proofs, Ma, Dai, and Shi [50] further reduced the resulting obfuscation and evaluation complexity to quasi-linear in the circuit size and proof size. Parallely, Diamond iO [25] 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 \(\mathrm{poly}(|C|)\). Notably, a recent work by Jain et al. [51] 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 \(k_{\text{lin}}\) 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. 5.2.3.

5.2.2 Quantum iO↩︎

Quantum iO is substantially less mature than classical iO. Alagic and Fefferman [52] 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. [53] 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 [54] 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. [55] obtained obfuscation for polynomial-size pseudo-deterministic quantum circuits in the classical-oracle model; Coladangelo and Gunn [56] 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 [57] constructed quantum state obfuscation for pseudo-deterministic quantum programs in the classical-oracle model, heuristically instantiable from quantum-secure classical iO. Huang and Tang [58] 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 [59] 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.

5.2.3 Hiding the GGM master key using fully succinct obfuscation↩︎

Jain, Jin, Mathialagan, and Paneth [51] introduce a fully succinct obfuscation notion for Turing machines with split descriptions. In this syntax, a program is written as \(M[\mathsf{pub}]\), where \(\mathsf{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 \(\mathsf{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 \(k_{\text{lin}}\).

To this end, we only need the fully succinct EF-iO, or equivalently the fully succinct pv-iO, guaranteed in [51], 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 [51]. We now verify the required EF-equivalence condition.

Let \(\mathcal{F}_\mathsf{master}\) be the GGM evaluation algorithm we use to construct our PPRF. Let \(\mathsf{Post}(y,k_y,\mathsf{pub})=(A_y,b_y)\) denote the deterministic polynomial-time post-processing algorithm used by our construction. Specifically, \(\mathsf{Post}\) takes the point \(y\), the GGM leaf key \(k_y:=\mathcal{F}_\mathsf{master}(k_{\text{lin}},y)\), and public parameters \(\mathsf{pub}\), and returns the matrix-vector pair \((A_y,b_y)\). We note that all randomness used by the post-processing is derived deterministically from the GGM output \(k_y\). Thus \(\mathsf{Post}\) is a deterministic polynomial-time computation and can be formalized in PV.

Fix a puncturing set \(S\subseteq \{0,1\}^r\), let \(k^S\) be the punctured key, and define the table of punctured values as \(\Delta_S:=\{(y,k_y): y\in S, k_y=\mathcal{F}_\mathsf{master}(k_{\text{lin}},y)\}\). We use \(\Delta_S[y]\) to denote the table lookup value \(k_y\) for \(y\in S\).

The set \(S\) is treated as part of the public description. The original PPRF program with the master key is \[\begin{align} M_{\mathsf{master}}[\mathsf{pub},S](y) := \mathsf{Post}(y,\mathcal{F}_\mathsf{master}(k_{\text{lin}},y),\mathsf{pub}). \end{align}\] The corresponding PPRF program with the punctured key is \[\begin{align} M_{\mathsf{punc}}[\mathsf{pub},S](y) := \begin{cases} \mathsf{Post}(y,\Delta_S[y],\mathsf{pub}), & \text{if } y\in S,\\[1.5mm] \mathsf{Post}(y,\mathcal{F}_\mathsf{punc}(k^S,y),\mathsf{pub}), & \text{if } y\notin S. \end{cases} \end{align}\] Here \(\mathcal{F}_\mathsf{punc}\) denotes the punctured GGM evaluation algorithm.

Now we show that the two programs \(M_{\mathsf{master}}[\mathsf{pub},S]\) and \(M_{\mathsf{punc}}[\mathsf{pub},S]\) agree on every input \(y\in\{0,1\}^r\). The proof is by case analysis. First, we suppose \(y\notin S\). By [51], the standard GGM construction of PPRF has a PV proof of puncturing correctness. Thus PV proves \[\begin{align} y\notin S \quad\Longrightarrow\quad \mathcal{F}_\mathsf{punc}(k^S,y)=\mathcal{F}_\mathsf{master}(k_{\text{lin}},y). \end{align}\] Since \(\mathsf{Post}\) is deterministic polynomial-time and formalizable in PV, PV is closed under substituting equal terms into \(\mathsf{Post}\). Therefore PV also proves \[\begin{align} y\notin S\quad\Longrightarrow\quad\mathsf{Post}(y,\mathcal{F}_\mathsf{punc}(k^S,y),\mathsf{pub})=\mathsf{Post}(y,\mathcal{F}_\mathsf{master}(k_{\text{lin}},y),\mathsf{pub}). \end{align}\] Hence \[\begin{align} y\notin S \quad\Longrightarrow\quad M_{\mathsf{punc}}[\mathsf{pub},S](y) = M_{\mathsf{master}}[\mathsf{pub},S](y). \end{align}\] Now suppose \(y\in S\). By construction of the table \(\Delta_S\), we have \[\begin{align} \Delta_S[y]=\mathcal{F}_\mathsf{master}(k_{\text{lin}},y). \end{align}\] Again, substituting this equality into the deterministic PV-formalizable function \(\mathsf{Post}\), PV proves \[\begin{align} y\in S\quad\Longrightarrow\quad\mathsf{Post}(y,\Delta_S[y],\mathsf{pub})=\mathsf{Post}(y,\mathcal{F}_\mathsf{master}(k_{\text{lin}},y),\mathsf{pub}). \end{align}\] Therefore \[\begin{align} y\in S \quad\Longrightarrow\quad M_{\mathsf{punc}}[\mathsf{pub},S](y) = M_{\mathsf{master}}[\mathsf{pub},S](y). \end{align}\] Combining the two cases, PV proves for every input \(y\in\{0,1\}^r\), \[\begin{align} M_{\mathsf{punc}}[\mathsf{pub},S](y) = M_{\mathsf{master}}[\mathsf{pub},S](y). \end{align}\] By the propositional translation theorem for PV (see [51], following Cook [60] and Cook–Reckhow [61]), this PV proof yields a uniform polynomial-size EF proof of the statement \[\begin{align} \forall y\in\{0,1\}^r,\qquad M_{\mathsf{punc}}[\mathsf{pub},S](y) = M_{\mathsf{master}}[\mathsf{pub},S](y). \end{align}\] 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 \(M_{\mathsf{master}}[\mathsf{pub},S]\) and \(M_{\mathsf{punc}}[\mathsf{pub},S]\) satisfy the same-size, same-runtime, and uniform-EF-equivalence conditions required for fully succinct EF-iO.

5.2.4 Conditional quantum obfuscation component↩︎

We stress that the obfuscation step used for hiding the classical GGM/PPRF master key \(k_{\text{lin}}\) 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 [51].

The situation is different for the main one-shot signature construction proposed in this work. In the original one-shot 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.

6 Conclusions↩︎

We have presented an explicit quantum-circuit implementation of a one-shot signature scheme, translating recent protocol-level constructions into concrete algorithms for \(\mathrm{\small KeyGen}\), \(\mathrm{\small Sign}\), and \(\mathrm{\small 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 \(\mathrm{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 \(\Theta(\kappa \log r+n+l)\) and gate complexity scaling as \(\Theta(n^3+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 \(\mathrm{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 \(\mathrm{PPRF}/\mathrm{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 \(\mathrm{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.

7 Acknowledgements↩︎

We acknowledge helpful discussions with Steven Duong.

References↩︎

---

1. We use the notation \(\xrightarrow{G}\) to denote the application of a quantum gate, \(G\); \(\xrightarrow{f}\) to denote the application of the classical function \(f\), implemented as a quantum query oracle, \(U_f |x, y\rangle = |x, y + f(x)\rangle\); and \(\xrightarrow{\mathrm{\small Circuit}}\) to denote the application of quantum circuit \(\mathrm{\small Circuit}\).↩︎