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, 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 $\hat{I}˜(\hat{I}º\log (r)+n+l)$ and the gate complexity scales like $\hat{I}˜(n^3+nl)$, where $r$ is the public key size, $n+l$ is the signature size, $l$ is the message size, and $\hat{I}º=\hat{I}\text{c◯}(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.

31 pages, 5 figures, and 5 tables