A quantum algorithm for one-shot signatures
Abstract
We provide a pre-obfuscation circuit-level implementation of an efficient one shot signature scheme, which has known applications to delegated signatures, secure token transfer, and publicly verifiable randomness. The algorithm consists of two stages: a key generation stage where a classical public key/quantum secret key pair is produced, and a signing stage where the quantum secret key is processed with a message string to produce a classical signature. There is no algorithmic error in the construction and the signed message can be efficiently checked by a classical verifier. Our scheme works by preparing a superposition over elements of a random affine coset determined by the output of a puncturable pseudorandom function, together with a circuit that tests coset membership. The logical qubit number scales like Θ( κlog(r) + n + l) and the gate complexity scales like Θ(n3 + nl), where r is the public key size, n+l is the signature size, l is the message size, and κ= Ω(n) is the cryptographic security parameter. We provide explicit qubit and gate counts before obfuscation. A secure instantiation additionally requires modified key generation and a security proof for the resulting obfuscated construction.
Versions
Related
- CNN-based algorithm for improving the quality of Single-Shot Holographic Tomography
- Shot noise signatures of Majorana-assisted transport in an Aharonov-Bohm interferometer
- Phase-sensitive avalanche quantum sensing of sub-shot-noise fields
- Extracting the anyon charge from shot noise in complex fractional quantum Hall edges
- Noise-regularized training of quantum circuit Born machines under a finite shot budget
BibTeX
@misc{muraleedharan2026quantum,
title = {{A quantum algorithm for one-shot signatures}},
author = {Gopikrishnan Muraleedharan and Minh Thuy Truc Pham and Vir Pathak and Thomas Gardner and Chuanqi Zhang and Samuel Crew and Tom Hartweg and Adrian Aasen and Guido Masella and Vase Moeini and Asier Piñeiro Orioli and Hugo Perrin and Gavin K. Brennen},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2606.23612},
eprint = {2606.23612},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2606.23612},
}
RIS
TY - UNPB
TI - A quantum algorithm for one-shot signatures
AU - Gopikrishnan Muraleedharan
AU - Minh Thuy Truc Pham
AU - Vir Pathak
AU - Thomas Gardner
AU - Chuanqi Zhang
AU - Samuel Crew
AU - Tom Hartweg
AU - Adrian Aasen
AU - Guido Masella
AU - Vase Moeini
AU - Asier Piñeiro Orioli
AU - Hugo Perrin
AU - Gavin K. Brennen
PY - 2026
DA - 2026/10/14
PB - arXiv
DO - 10.48550/arxiv.2606.23612
UR - https://arxiv.org/abs/2606.23612
AB - We provide a pre-obfuscation circuit-level implementation of an efficient one shot signature scheme, which has known applications to delegated signatures, secure token transfer, and publicly verifiable randomness. The algorithm consists of two stages: a key generation stage where a classical public key/quantum secret key pair is produced, and a signing stage where the quantum secret key is processed with a message string to produce a classical signature. There is no algorithmic error in the construction and the signed message can be efficiently checked by a classical verifier. Our scheme works by preparing a superposition over elements of a random affine coset determined by the output of a puncturable pseudorandom function, together with a circuit that tests coset membership. The logical qubit number scales like Θ( κlog(r) + n + l) and the gate complexity scales like Θ(n^3 + nl), where r is the public key size, n+l is the signature size, l is the message size, and κ= Ω(n) is the cryptographic security parameter. We provide explicit qubit and gate counts before obfuscation. A secure instantiation additionally requires modified key generation and a security proof for the resulting obfuscated construction.
ER -