A quantum algorithm for one-shot signatures

arXiv:2606.23612v2 Announce Type: replace 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 $\Theta( \kappa\log(r) + n + l)$ and the gate complexity scales like $\Theta(n^3 + nl)$, where $r$ is the public key size, $n+l$ is the signature size, $l$ is the message size, and $\kappa = \Omega(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.

Authors:Gopikrishnan Muraleedharan, Minh Thuy Truc Pham, Vir Pathak, Thomas Gardner, Chuanqi Zhang, Samuel Crew, Tom Hartweg, Adrian Aasen, Guido Masella, Vase Moeini, Asier Piñeiro Orioli, Hugo Perrin, Gavin K. Brennen

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 $\Theta( \kappa\log(r) + n + l)$ and the gate complexity scales like $\Theta(n^3 + nl)$, where $r$ is the public key size, $n+l$ is the signature size, $l$ is the message size, and $\kappa = \Omega(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.

32 pages, 5 figures, and 5 tables. Accepted for publication at ACM PQQS 2026

Quantum Physics (quant-ph); Cryptography and Security (cs.CR)

arXiv:2606.23612 [quant-ph]

(or arXiv:2606.23612v2 [quant-ph] for this version)

https://doi.org/10.1145/3839338.3857255 DOI(s) linking to related resources

aiqbench analysis

A quantum algorithm for one-shot signatures

Related coverage