A quantum algorithm for one-shot signatures
Authors:
- Gopikrishnan MuraleedharanGMGopikrishnan Muraleedharan
- Minh Thuy Truc PhamMPMinh Thuy Truc Pham
- Vir PathakVPVir Pathak
- Thomas GardnerTGThomas Gardner
- Chuanqi ZhangCZChuanqi Zhang
- Samuel CrewSCSamuel Crew
- Tom HartwegTHTom Hartweg
- Adrian AasenAAAdrian Aasen
- Guido MasellaGMGuido Masella
- Vase MoeiniVMVase Moeini
- Asier Piñeiro OrioliAOAsier Piñeiro Orioli
- Hugo PerrinHPHugo Perrin
Open Access
- 2 November 2026
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 132-147
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.Keywords
This publication has 25 references indexed in Scilit:
- On Succinct Obfuscation via Propositional Proofs2025
- On One-Shot Signatures, Quantum vs. Classical Binding, and Obfuscating Permutations2025
- Undermining Quantum Circuit Obfuscation: Insights from Structural Analysis2025
- Grover on $\,SIMON\,$Quantum Information Processing, 2020
- Candidate Indistinguishability Obfuscation and Functional Encryption for All CircuitsSIAM Journal on Computing, 2016
- The two-sided infinite extension of the Mallows model for random permutationsAdvances in Applied Mathematics, 2012
- Algorithms for quantum computation: discrete logarithms and factoring2002
- Time/Space Trade-Offs for Reversible ComputationSIAM Journal on Computing, 1989
- Representations of finite groups of Lie typeBulletin of the American Mathematical Society, 1979
- NON-NULL RANKING MODELS. IBiometrika, 1957