Unclonable Cryptography in Linear Quantum Memory Enables Single-Message Signing Without Persistent Key Storage

Unclonable cryptography represents a rapidly developing field that harnesses quantum information to achieve security beyond the reach of classical methods, and it relies on the fundamental principle that quantum states cannot be perfectly copied. Omri Shmueli from NTT Research and Mark Zhandry address a critical challenge in this area, namely the substantial memory requirements for storing cryptographic keys in long-lived quantum systems. Their work focuses on one-shot signatures and signing tokens, important unclonable primitives where keys allow signing a single message only, and they demonstrate a significant reduction in the size of these secret keys, achieving near-optimal efficiency in some cases. By developing novel techniques for proving security using coset states, they advance the practicality of quantum cryptography and pave the way for more efficient and secure communication systems.

To achieve decoherence, persistent quantum memory represents one of the most challenging resources for quantum computers. Consequently, minimising persistent memory in quantum protocols is critically important. This work considers the case of one-shot signatures (OSS) and, more generally, quantum signing tokens. These are important unclonable primitives, where quantum signing keys allow for signing a single message, but not two. Naturally, these quantum signing keys would require storage in long-term quantum memory. Very recently, the first OSS was constructed both in a classical oracle model and in the standard model, but the team observes that the quantum memory required for these protocols was quite large.

Quantum Primitives, Security and Cryptography

This collection of research papers explores the rapidly evolving field of cryptography, with a particular focus on quantum cryptography, obfuscation, and related concepts. The research investigates how quantum mechanics can enhance cryptographic security and address limitations of classical methods. Key themes include quantum cryptographic primitives like quantum money and one-time signatures, cryptographic obfuscation to hide program structure, and the creation of unclonable cryptographic keys resistant to copying. Researchers also explore advanced concepts such as lossy trapdoor functions and succinct non-interactive arguments of knowledge (SNARGs), alongside the crucial challenge of developing cryptographic algorithms resistant to attacks from quantum computers.

The research highlights several key contributions. Studies explore the design and security of quantum money schemes, leveraging quantum mechanics to create banknotes impossible to counterfeit. Investigations into quantum one-time programs explore quantum analogs of classical programs for secure computation. Researchers also examine quantum analogs of the Bitcoin Lightning Network to improve blockchain scalability and quantum prudent contracts to prevent malicious behavior. Many papers focus on indistinguishability obfuscation (iO), a crucial building block for secure cryptographic systems, and adaptive security in SNARGs, building proofs secure against sophisticated adversaries.

Studies also explore the obfuscation of unitary quantum programs, addressing the unique challenges of hiding quantum program structure. The research also investigates unclonable cryptography, using physical unclonable functions (PUFs) to create decryption keys difficult to clone and building unclonable cryptographic systems resistant to collusion attacks. Several papers explore the design and security of one-shot signature schemes, with applications in various cryptographic protocols, and the use of quantum mechanics to create commitments binding to the committer. Finally, the research addresses post-quantum cryptography, developing lossy trapdoor functions and SNARGs resistant to attacks from quantum computers. Overall, the research demonstrates a growing trend towards hybrid approaches combining classical and quantum techniques, increased emphasis on physical security measures, and formal verification of cryptographic protocols.

Smaller Quantum Keys Enable Secure Signatures

This work presents a significant advancement in quantum cryptography, specifically concerning the size of secret keys required for one-shot signatures (OSS) and signing tokens. Researchers achieved a substantial reduction in the quantum memory needed for these unclonable primitives, bringing the key size closer to the theoretical minimum. The team developed novel techniques for proving the security of cryptosystems using coset states, which are fundamental to many quantum cryptographic protocols. The breakthrough centers on a new approach to signing, where the entire message is signed using a single, small quantum state in a parallel process, contrasting with previous methods requiring larger keys.

The team’s analysis of an existing OSS construction revealed that the generated states could be reduced to a size of Ω(λ)0. 4, a significant improvement over the previously required Ω(λ2). This optimization stems from a refined security reduction and a more efficient analysis of the underlying cryptographic principles. Measurements confirm that the new approach achieves a key size directly proportional to the security parameter λ, meaning the best attack time or the ratio of attack time to success probability remains exponential in the key length. The team demonstrated this by embedding a collision-resistant function within the oracles used in the OSS construction, carefully managing its input size to minimize the required quantum memory.

Previously, achieving a pre-image set size of 2λ required applying λ separate 2-to-1 functions in parallel, resulting in an input size of λ2; this work streamlines this process. The research delivers a substantial reduction in the quantum resources needed for secure signing, paving the way for more practical and efficient quantum cryptographic systems. This advancement has implications for various applications, including quantum copy protection and quantum one-time programs, and opens new avenues for exploration in the field of unclonable cryptography.

Optimal Quantum Signatures With Coset States

This work presents significant advances in the construction of one-shot signatures and signing tokens, cryptographic primitives requiring unclonable keys stored in long-term quantum memory. Researchers addressed the challenge of minimizing the size of these quantum keys, which is crucial given the susceptibility of quantum states to decoherence. By developing novel techniques for proving the security of cryptosystems using coset states, the team substantially reduced the required key size, achieving asymptotically optimal performance in certain cases. The researchers’ approach centers on a new signing method that utilizes a single, small quantum state to sign entire messages in parallel.

This innovation, combined with a refined analysis of existing one-shot signature constructions, resulted in a significant reduction in the size of generated states. Specifically, they demonstrated that states can be generated with a size of O(λ)0. 4, a considerable improvement over previous constructions requiring O(λ2) size, where λ represents the security parameter. This achievement represents a step towards practical quantum cryptographic systems by lessening the demands on persistent quantum memory. The authors acknowledge that their analysis relies on certain cryptographic assumptions and that further research is needed to explore the full potential of their techniques. They suggest that their methods may be applicable to other areas of quantum cryptography, such as quantum copy protection and quantum one-time programs, offering a promising avenue for future investigation. The team emphasizes the importance of minimizing quantum key size, and their work provides a valuable contribution to the development of more efficient and robust quantum cryptographic protocols.