New One-Shot Signature Construction Extends Cryptography Beyond Classical Oracle Models

The possibility of creating a digital signature valid for only one message has long been considered impossible using classical cryptography, yet recent theoretical work suggests it might be achievable by exploiting the laws of quantum physics. Omri Shmueli from NTT Research and Mark Zhandry, affiliated with both NTT Research and Stanford University, now present the first practical construction of such a ‘one-shot signature’ that functions securely in standard cryptographic models. Their work resolves a significant open problem and builds upon the initial concept introduced by Amos and colleagues, overcoming a critical flaw in their earlier design. This breakthrough not only establishes the feasibility of one-shot signatures but also provides the first definitive separation between classical and collapse-binding cryptographic commitments, a challenge that has occupied researchers for over a decade, and unlocks a new approach to constructing essential cryptographic tools like full-domain trapdoor permutations.

Quantum One-Shot Signatures and Cryptographic Commitments

One-shot signatures (OSS) represent a fascinating and challenging concept in cryptography, offering the possibility of signing exactly one message with a key that self-destructs afterward. While classically impossible, OSS may be achievable using quantum mechanics, potentially revolutionizing areas like smart contracts and blockchain technology. This spurred significant research into alternative approaches and a deeper understanding of the underlying cryptographic principles. The difficulty in constructing OSS is linked to the broader challenge of creating secure cryptographic commitments in a world threatened by quantum computers.

Establishing the existence of OSS, therefore, also addresses a decade-old open problem in post-quantum cryptography, potentially safeguarding future cryptographic systems against emerging quantum threats. The pursuit of OSS is not merely theoretical; it promises solutions to scalability issues in blockchain technology and opens doors to entirely new cryptographic applications. Recent research has focused on constructing OSS in a “standard model,” meaning without relying on potentially unrealistic assumptions. This work introduces new cryptographic tools, including a concept called “permutable pseudorandom permutations,” and demonstrates how to translate existing cryptographic proofs into more robust, obfuscation-based proofs.

This approach moves beyond the limitations of previous constructions and offers a promising path toward realizing the full potential of one-shot signatures. This new research not only provides the first standard-model OSS but also resolves another long-standing problem in cryptography: the construction of a specific type of “full-domain” trapdoor one-way permutation. By leveraging the concept of permutable pseudorandom permutations and combining it with indistinguishability obfuscation, researchers have achieved a breakthrough that has eluded the field for years.

Indistinguishability Obfuscation Enables One-Shot Signatures

Researchers have developed a novel approach to creating one-shot signatures, a cryptographic tool allowing a key to sign only one message before being destroyed. Previous attempts at constructing these signatures faced fundamental limitations, particularly in proving their security without relying on unproven assumptions. This new methodology overcomes these hurdles by leveraging a technique called indistinguishability obfuscation, combined with the well-studied assumption of Learning With Errors. A key innovation lies in the creation of “permutable pseudorandom permutations,” a special type of cryptographic building block that allows for controlled rearrangements of data while maintaining a high degree of randomness.

The team demonstrates how obfuscating these permutable permutations yields a “full-domain” trapdoor one-way permutation, solving a decade-old problem of constructing such an object from standard cryptographic tools. The researchers also address a known barrier in constructing one-way permutations from obfuscation and one-way functions, specifically the issue of “domain invariance.” They demonstrate that their construction avoids the limitations highlighted in previous work, clarifying the boundaries of what is achievable with current cryptographic techniques. Furthermore, the team’s approach opens avenues for future research, including exploring the possibility of achieving one-shot signatures without relying on sub-exponential hardness assumptions and investigating whether a “clean” implementation using only indistinguishability obfuscation and basic cryptographic primitives is possible. This work represents a significant step forward in the development of secure and practical one-shot signatures, with potential applications in a wide range of decentralized systems and cryptographic protocols.

First Standard-Model One-Shot Signature Constructed

Researchers have achieved a significant breakthrough in cryptography by constructing the first standard-model one-shot signature (OSS), a digital signature scheme that allows signing only a single message. Originally proposed as a potentially quantum-enabled technology, OSS had remained unproven even in theoretical models due to a critical flaw discovered in the only existing candidate construction. This new result definitively establishes the feasibility of OSS using established cryptographic tools, specifically indistinguishability obfuscation and the Learning With Errors problem. The concept of a one-shot signature is counterintuitive, as classical cryptography assumes the ability to sign multiple messages.

However, OSS leverages the principle that signing a message irrevocably destroys the signing key, preventing further signatures. This has implications for various applications, including secure smart contracts, improved consensus protocols, and potentially even quantum money schemes. Previous attempts to construct OSS relied on a flawed proof, leaving its existence uncertain. This new work not only provides a correct construction but also resolves a decade-old problem in cryptographic commitment schemes. Researchers demonstrate a clear separation between classical and collapse-binding commitments, addressing a vulnerability that could arise with post-quantum cryptographic systems.

The construction relies on a novel cryptographic primitive called permutable pseudorandom permutations, and demonstrates how obfuscating these permutations yields a full-domain trapdoor permutation. This is a significant advancement, as constructing such permutations had remained an open problem for over ten years. By establishing the existence of OSS and resolving related cryptographic challenges, this research provides a solid foundation for exploring its potential applications and advancing the field of secure computation.

One-Shot Signatures From Standard Assumptions

This research presents the first standard-model one-shot signature (OSS) scheme, a cryptographic tool allowing a key to sign only one message before being destroyed, and resolves a decade-old open problem in cryptography. Previous attempts at constructing OSS relied on flawed proofs or required quantum oracles, making them impractical or unproven in standard cryptographic models. This new construction is justified assuming the existence of indistinguishability obfuscation and the Learning with Errors problem, both well-studied cryptographic assumptions. The significance of this work extends beyond the creation of OSS itself.

It also establishes the first standard-model separation between classical and collapse-binding commitments and hashing, clarifying a fundamental relationship in cryptographic design. This separation demonstrates that classical security notions are insufficient in a quantum world, necessitating stronger, quantum-resistant approaches to commitment schemes. The authors acknowledge that their construction relies on specific cryptographic assumptions, and the practicality of implementing it remains to be explored. They also note that while their work resolves a theoretical separation, further research is needed to understand the implications for real-world cryptographic protocols fully. Future work could focus on optimizing the efficiency of the scheme and investigating its applicability to various decentralized applications.