Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper introduces a quantum algorithm for one-shot signatures that combines classical and quantum cryptographic techniques to enhance security in delegated signatures and token transfers. The proposed method features a two-stage process involving key generation and signing, ensuring efficient verification by classical systems without algorithmic errors. Key results include detailed scaling analysis of logical qubit numbers and gate complexity, demonstrating the algorithm's practicality against both classical and quantum attacks.
A quantum one-shot signature scheme achieves efficient security with no algorithmic errors, paving the way for robust delegated signatures and verifiable randomness.
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.