{"ID":2856034,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2510.10899","arxiv_id":"2510.10899","title":"A Simple and Efficient One-Shot Signature Scheme","abstract":"One-shot signatures (OSS) are a powerful and uniquely quantum cryptographic primitive which allows anyone, given common reference string, to come up with a public verification key $\\mathsf{pk}$ and a secret signing state $|\\mathsf{sk}\\rangle$. With the secret signing state, one can produce the signature of any one message, but no more. In a recent breakthrough work, Shmueli and Zhandry (CRYPTO 2025) constructed one-shot signatures, either unconditionally in a classical oracle model or assuming post-quantum indistinguishability obfuscation and the hardness of Learning with Errors (LWE) in the plain model. In this work, we address the inefficiency of the Shmueli-Zhandry construction which signs messages bit-by-bit, resulting in signing keys of $Θ(λ^4)$ qubits and signatures of size $Θ(λ^3)$ bits for polynomially long messages, where $λ$ is the security parameter. We construct a new, simple, direct, and efficient one-shot signature scheme which can sign messages of any polynomial length using signing keys of $Θ(λ^2)$ qubits and signatures of size $Θ(λ^2)$ bits. We achieve corresponding savings in runtimes, in both the oracle model and the plain model. In addition, unlike the Shmueli-Zhandry construction, our scheme achieves perfect correctness. Our scheme also achieves strong signature incompressibility, which implies a public-key quantum fire scheme with perfect correctness among other applications, correcting an error in a recent work of Çakan, Goyal and Shmueli (QCrypt 2025) and recovering their applications.","short_abstract":"One-shot signatures (OSS) are a powerful and uniquely quantum cryptographic primitive which allows anyone, given common reference string, to come up with a public verification key $\\mathsf{pk}$ and a secret signing state $|\\mathsf{sk}\\rangle$. With the secret signing state, one can produce the signature of any one mess...","url_abs":"https://arxiv.org/abs/2510.10899","url_pdf":"https://arxiv.org/pdf/2510.10899v1","authors":"[\"Andrew Huang\",\"Vinod Vaikuntanathan\"]","published":"2025-10-13T01:53:00Z","proceeding":"quant-ph","tasks":"[\"quant-ph\",\"cs.CR\"]","methods":"[]","has_code":false}