A quantum algorithm for one-shot signatures
2026-06-22 • Cryptography and Security
Cryptography and Security
AI summaryⓘ
The authors present a way to build a special kind of digital signature using quantum circuits that can be used once and then thrown away. Their method involves creating a pair of keys: a public one that everyone can see, and a secret quantum one that is used to make signatures. The signatures can then be checked by ordinary classical computers without mistakes. They carefully analyze how many quantum bits and operations are needed, and point out where extra protections would be needed to keep the system secure against hackers using both classical and quantum computers.
one shot signaturequantum secret keypublic keydigital signaturequantum circuitpuncturable pseudorandom functioncoset membershipquantum cryptographygate complexitysecurity parameter
Authors
Gopikrishnan Muraleedharan, Minh Thuy Truc Pham, Vir Pathak, Thomas Gardner, Chuanqi Zhang, QPerfect, 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, secured 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 for varying $n$ and identify the circuit components where obfuscation would be required for security against classical and quantum polynomial time attacks.