A quantum algorithm for one-shot signatures

The gist The paper provides a pre-obfuscation circuit-level implementation of an efficient one shot signature scheme, which has known applications to delegated signatures, secured token transfer, and publicly verifiable randomness.

Introduction and Motivation

The study of quantum algorithms is frequently framed within the context of computational complexity where seminal protocols 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 constructive paradigm is best exemplified by “local quantum cryptography” which restricts operations entirely to local quantum computation and classical communication. Crucially, this framework eliminates the need for a quantum internet 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.

One-Shot Signature (OSS) Scheme Definition

A One-Shot Signature (OSS) scheme is an asymmetric digital signature scheme satisfying the oneshot property Concretely, an entity that has a quantum computer generates a pair consisting of a quantum secret key and a corresponding classical public key. Because the secret key is a quantum state intended for a single use, reusing it is physically impossible: once used to sign a message, the state collapses upon measurement and the measurement output is the classical signature; hence, the key is irreversibly destroyed in the process. This physical destruction ensures that the key cannot be reused, copied, or duplicated after signing.

Key Generation and Circuit Components

The key generation stage involves sampling a uniform superposition over states from a random affine coset determined by the output of a puncturable pseudorandom function. The algorithm consists of two stages: a key generation stage where a classical public key/quantum secret key pair is produced, and a signing stage where the quantum secret key is processed with a message string to produce a classical signature. The quantum key generation involves sampling a uniform superposition over states from a random affine subspace. The final sum is over the entire secret coset that F associates with y

Signing Procedure for Multi-Bit Messages

The signing procedure can be streamlined using a global approach, replacing the repeated single-bit signing structure with a global measurement and a single translation step To sign an l-bit message m in Zl2 using a global approach, the signer performs a simultaneous computational basis measurement of the first l qubits of the state ψ⟩ If p!= m, the signer applies a global translation operator XL to the entire (n+l) qubit post-measurement state to shift the state into the target subspace associated with the message m The oracle Dp→m leverages the Fourier shift theorem to account for displacement across all l message dimensions simultaneously.

Verification and Security Analysis

The verification algorithm is a classical, deterministic polynomial-time procedure that checks the validity of the signature against a message m and a public key y The verification workflow proceeds through a sequence of classical algorithmic steps, leveraging the parameters from the CRS. The final signature σ must take the form σ = By(m + b(l)y) + Ayz + b(n)y for some z, which confirms that the measured signature σ is valid and consistent with both the message m and the public key y. The security of most existing OSS constructions relies on the assumption of sub-exponentially secure Indistinguishability Obfuscation (iO).

Logical Resource Analysis

The logical qubit complexity scales as Θ(κ log r+n+l) and the gate complexity scales as Θ(n 3+nl) The total logical qubit count is given by the formula in Eq. 4.2, which is n + 2l + r + κ⌈lg(r + 2)⌉.

Security Parameter Selection

The cryptographic security parameter κ must be selected carefully because if κ is small, a quantum adversary can recover the PRF key klin using Grover search in O(2κ/2) oracle queries. The value of κ is derived using the bound given in (SZ25a, Lemma 26, Lemma 56) guarantee that an adversary A cannot tamper with the obfuscated circuit associated with these superspaces in order to exploit the collisions of the underlying hash function

Obfuscation Requirements

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 However, the modified key generation step requires an obfuscator for the relevant class of quantum circuits. Thus, this work clarifies both the practical algorithmic structure of OSS and the remaining bottleneck for a full plain-model instantiation: the development of efficient and secure quantum obfuscation tools.

Conclusion

We have presented an explicit quantum-circuit implementation of a one-shot signature scheme, translating recent protocol-level constructions into concrete algorithms for KeyGen, Sign, and Verify. The construction prepares the quantum signing key as a uniform superposition over a hidden affine coset determined by a puncturable pseudorandom function, and realizes the required arithmetic using a GGM-based lookup together with reversible linear-algebra subroutines. We 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.

Acknowledgements

We acknowledge helpful discussions with Steven Duong

References

[AC12] Scott Aaronson and Paul Christiano. Quantum money from hidden subspaces. In Proceedings of the Forty-Fourth Annual ACM Symposium on Theory of Computing, STOC ’12, page 41–60, New York, NY, USA, 2012.

[AGKZ20] Ryan Amos, Marios Georgiou, Aggelos Kiayias, and Mark Zhandry. One-shot signatures and applications to hybrid quantum/classical authentication. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, page 255–268, New York, NY, USA, 2020.

[Ala16] Alagic, Gorjan and Fefferman, Bill. On quantum obfuscation. arXiv preprint arXiv:1602.01771, 2016.

[Ala21] Alagic, Gorjan and Brakerski, Zvika and Dulek, Yfke and Schaffner, Christian. Impossibility of quantum virtual black-box obfuscation of classical circuits. In Annual International Cryptology Conference, pages 497–525. Springer, 2021.

[AMM20] Ravi Anand, Arpita Maitra, and Sourav Mukhopadhyay. Grover on SIMON. Quantum Information Processing, 19(9):340, 2020.

[Ana14] Ananth, Prabhanjan and Gupta, Divya and Ishai, Yuval and Sahai, Amit. Optimizing obfuscation: avoiding barrington’s theorem. In Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security, pages 646–658, 2014.

[Ana17] Ananth, Prabhanjan and Jain, Abhishek and Sahai, Amit. Indistinguishability obfuscation for turing machines: constant overhead and amortization. In Annual International Cryptology Conference, pages 252–279. Springer, 2017.

[Bar12] Barak, Boaz and Goldreich, Oded and Impagliazzo, Russell and Rudich, Steven and Sahai, Amit and Vadhan, Salil and Yang, Ke. On the (im)possibility of obfuscating programs. J. ACM, 59(2), May 2012.

[Bar23] Bartusek, James and Kitagawa, Fuyuki and Nishimaki, Ryo and Yamakawa, Takashi. Obfuscation of pseudodeterministic quantum circuits. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, pages 1567–1578, 2023.

[Bar24] Bartusek, James and Brakerski, Zvika and Vaikuntanathan, Vinod. Quantum state obfuscation from classical oracles. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing, pages 1009–1017, 2024.

[BDJ+24] Pedro Branco, Nico D¨ottling, Abhishek Jain, Giulio Malavolta, Surya Mathialagan, Spencer Peters, and Vinod Vaikuntanathan. Pseudorandom obfuscation and applications.

1. Bold Header: Quantum One-Shot Signature Implementation

This implementation allows for delegated signatures, secured token transfer, and publicly verifiable randomness by preparing a superposition over elements of a random affine coset determined by the output of a puncturable pseudorandom function.

2. Bold Header: Streamlined Multi-bit Signing

The algorithm uses a global measurement and a single translation using one multi-control phase gate instead of l instances thereof to sign longer messages, reducing complexity compared to iterative bit-flipping.

3. Bold Header: Enhanced Security via Obfuscation Layer

The system separates the implementation into classical iO for the PPRF/GGM subroutines and a quantum obfuscation layer for the Hadamard-based signing component, clarifying where future quantum iO tools are needed.