A Simple and Efficient One-Shot Signature Scheme

• URL: http://arxiv.org/abs/2510.10899v1
• Date: Mon, 13 Oct 2025 01:53:00 GMT
• Title: A Simple and Efficient One-Shot Signature Scheme
• Authors: Andrew Huang, Vinod Vaikuntanathan,
• Abstract summary: One-shot signatures (OSS) are a powerful and uniquely quantum cryptographic primitive.<n>We construct a new, simple, direct, and efficient one-shot signature scheme which can sign messages of any length.<n>Unlike the Shmueli-Zhandry construction, our scheme achieves perfect correctness.
• Score: 7.043920979018913
• License: http://creativecommons.org/licenses/by/4.0/
• 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 $\Theta(\lambda^4)$ qubits and signatures of size $\Theta(\lambda^3)$ bits for polynomially long messages, where $\lambda$ 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 $\Theta(\lambda^2)$ qubits and signatures of size $\Theta(\lambda^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 \c{C}akan, Goyal and Shmueli (QCrypt 2025) and recovering their applications.

Related papers

• Spinel: A Post-Quantum Signature Scheme Based on $\mathrm{SL}_n(\mathbb{F}_p)$ Hashing [1.6930974360601116]
  We introduce Spinel, a post-quantum digital signature scheme with security rooted in the hardness of navigating expander graphs over $mathrmSL_n(mathbbF_p)$.<n>Our approach lays the foundations for the design of hash-based signature schemes, expanding the toolkit of post-quantum cryptography.
  arXiv  Detail & Related papers  (2026-02-10T15:22:01Z)
• MIRANDA: short signatures from a leakage-free full-domain-hash scheme [10.228787876075266]
  We present $mathsfMiranda$, the first family of full-domain-hash signatures based on matrix codes.<n>Our trapdoor is very simple and generic: if we propose it with matrix codes, it can actually be instantiated in many other ways.
  arXiv  Detail & Related papers  (2025-10-08T19:24:24Z)
• Extending Asynchronous Byzantine Agreement with Crusader Agreement [23.27199615640474]
  We present a new reduction from multivalued BA to binary BA.<n>As our reduction uses multivalued CA, we also design two new information-theoretic CA protocols for $ell$-bit inputs.
  arXiv  Detail & Related papers  (2025-02-04T13:44:41Z)
• On the (In)security of optimized Stern-like signature schemes [0.5755004576310334]
  A crucial optimization of Stern's signature scheme is to generate pseudo-random vectors and a permutation instead of random ones. We show that for some parameters, there is an attack that exploits this optimization and breaks the scheme in time. By adding a string $salt in 0,12lambda$ to the scheme, and changing slightly how the pseudo-random strings are generated, we prove not only that our attack doesn't work but that for any attack, the scheme preserves $lambda$ bits of security.
  arXiv  Detail & Related papers  (2024-08-28T15:03:38Z)
• Superposed Decoding: Multiple Generations from a Single Autoregressive Inference Pass [72.07642648108849]
  Superposed Decoding is a new decoding algorithm that generates $k$ drafts at the cost of one autoregressive inference pass. Superposed Decoding can be combined with other decoding strategies, resulting in universal coverage gains when scaling inference time compute.
  arXiv  Detail & Related papers  (2024-05-28T17:40:48Z)
• SQIAsignHD: SQIsignHD Adaptor Signature [0.6708691048956046]
  We introduce $mathsfSQIAsignHD$, a new quantum-resistant adaptor signature scheme based on isogenies of supersingular elliptic curves.<n>We exploit the idea of the artificial orientation on the supersingular isogeny Diffie-Hellman key exchange protocol, SIDH, to define the underlying hard relation.
  arXiv  Detail & Related papers  (2024-04-13T15:25:28Z)
• A Construction of Evolving $k$-threshold Secret Sharing Scheme over A Polynomial Ring [55.17220687298207]
  The threshold secret sharing scheme allows the dealer to distribute the share to every participant that the secret is correctly recovered from a certain amount of shares. We propose a brand-new construction of evolving $k$-threshold secret sharing scheme for an $ell$-bit secret over a ring, with correctness and perfect security.
  arXiv  Detail & Related papers  (2024-02-02T05:04:01Z)
• Revocable Quantum Digital Signatures [57.25067425963082]
  We define and construct digital signatures with revocable signing keys from the LWE assumption. In this primitive, the signing key is a quantum state which enables a user to sign many messages. Once the key is successfully revoked, we require that the initial recipient of the key loses the ability to sign.
  arXiv  Detail & Related papers  (2023-12-21T04:10:07Z)
• Tokenization and the Noiseless Channel [71.25796813073399]
  Good tokenizers lead to emphefficient channel usage, where the channel is the means by which some input is conveyed to the model. In machine translation, we find that across multiple tokenizers, the R'enyi entropy with $alpha = 2.5$ has a very strong correlation with textscBleu: $0.78$ in comparison to just $-0.32$ for compressed length.
  arXiv  Detail & Related papers  (2023-06-29T10:32:09Z)
• Revocable Cryptography from Learning with Errors [61.470151825577034]
  We build on the no-cloning principle of quantum mechanics and design cryptographic schemes with key-revocation capabilities. We consider schemes where secret keys are represented as quantum states with the guarantee that, once the secret key is successfully revoked from a user, they no longer have the ability to perform the same functionality as before.
  arXiv  Detail & Related papers  (2023-02-28T18:58:11Z)
• Unclonable Encryption, Revisited [7.129830575525267]
  Unclonable encryption, introduced by Broadbent and Lord (TQC'20), is an encryption scheme with the following attractive feature. We construct unclonable encryption schemes with semantic security. We show that unclonable encryption implies copy-protection for a simple class of unlearnable functions.
  arXiv  Detail & Related papers  (2021-03-27T22:37:59Z)
• Quantum copy-protection of compute-and-compare programs in the quantum random oracle model [48.94443749859216]
  We introduce a quantum copy-protection scheme for a class of evasive functions known as " compute-and-compare programs" We prove that our scheme achieves non-trivial security against fully malicious adversaries in the quantum random oracle model (QROM) As a complementary result, we show that the same scheme fulfils a weaker notion of software protection, called "secure software leasing"
  arXiv  Detail & Related papers  (2020-09-29T08:41:53Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.