Lattice-based Traceable Signatures Offer Provable Security in the Random Oracle Model

Traceable signatures offer a powerful way to balance anonymity with accountability in digital communication, allowing the revealing of a signer’s identity when necessary, and Nam Tran, Khoa Nguyen, and Dongxi Liu, alongside Josef Pieprzyk and Willy Susilo, now present a fundamentally new approach to building these systems. Existing traceable signature schemes rely on complex mathematical problems related to numbers and pairings, which pose challenges for implementation on standard computers, and potentially limit their widespread use. This research overcomes these limitations by constructing a traceable signature scheme based on lattices, a different and increasingly important area of cryptography, and importantly, proves its security within a well-established security framework, offering a robust and practical alternative for anonymous authentication. The team’s work establishes a new direction for traceable signature design, paving the way for more efficient and widely deployable privacy-preserving technologies.

The research explores the tracing power of opening authority in group signatures. Existing traceable signature constructions rely on number-theoretical or pairing assumptions, potentially leaving them vulnerable to attacks from quantum computers. This work revisits the concept of traceable signatures and presents a new construction based on lattices, offering provable security within the quantum random oracle model. This approach provides a post-quantum alternative, enhancing the security of digital signature schemes, particularly within group signature systems.

Lattice-Based Traceable Signatures for Post-Quantum Security

This research presents a novel lattice-based construction of traceable signatures, addressing a gap in existing systems reliant on number-theoretic or pairing assumptions. The team engineered a system designed to operate securely even in a post-quantum computing environment, a critical advancement for long-term security applications. The core of this work lies in a carefully constructed cryptographic scheme encompassing algorithms for setup and verification, extending the functionality of dynamic group signatures with formalized tracing and claiming mechanisms. Scientists developed a method where the group manager first executes an algorithm to obtain a user-specific tracing trapdoor, a unique piece of information associated with each user.

This trapdoor empowers authorized parties to identify signatures originating from a specific user without compromising the anonymity of others. Simultaneously, the team implemented an algorithm allowing users to publicly assert authorship of previously issued signatures using their signing keys, with public verification achieved through a corresponding verification algorithm. The study rigorously evaluated the security of this system, focusing on traceability, non-frameability, and anonymity, mirroring the security goals of traditional group signatures but with nuanced considerations for tracing and claiming. Researchers demonstrated that the system prevents a dishonest group manager from forging signatures traced to honest users and ensures users cannot falsely claim authorship of signatures they did not create, even when colluding with the group manager. This construction achieves provable security in the random oracle model, offering a robust and efficient solution for applications requiring enhanced accountability and privacy. The team’s approach delivers a significant improvement over existing lattice-based schemes, establishing a new benchmark for post-quantum traceable signatures.

Lattice-Based Zero-Knowledge Proof for Signatures

This research details a complex zero-knowledge proof system designed to verify a signature scheme. The goal is to allow a signer to prove to a verifier that they possess a valid signature for a message without revealing the private key used to create it, crucial for maintaining privacy and security. The system builds upon several cryptographic foundations, including lattice-based problems like Short Integer Solution and Learning With Errors, and a specific type of encryption called Identity-Based Encryption. The core idea involves transforming complex cryptographic statements into a set of simple quadratic equations.

These equations represent the relationships between cryptographic variables, such as the signature, private key, and message. By expressing these relationships mathematically, the system can leverage efficient zero-knowledge proof protocols to verify the validity of the signature. The complexity of the system is analyzed in terms of the security parameter, the size of the lattice used, and the number of constraints. The researchers claim that the size of the proof grows logarithmically with the security parameter, meaning it increases relatively slowly. This is a significant achievement, as smaller proof sizes lead to faster verification times, reduced communication costs, and improved scalability. The work demonstrates a sophisticated construction of a zero-knowledge proof system for a lattice-based signature scheme, offering a potentially practical solution for real-world applications.

Lattice Signatures Enable Traceable Group Membership

This work presents a new construction of traceable signatures based on lattice cryptography, offering an alternative to existing schemes reliant on number-theoretic or pairing assumptions. The researchers demonstrate a provably secure system within the random oracle model, achieving improved soundness error compared to previous approaches employing Stern-like zero-knowledge proofs. Notably, the design allows for nearly constant signature size when the group membership is predetermined, representing a practical advantage in certain applications. The achievement lies in successfully translating concepts from verifiable lattice-based relations into the domain of traceable signatures, and establishing a link between dynamic group signatures and traceable signature schemes. The team acknowledges that transforming standard verifiable lattice-based relations into traceable signatures is not straightforward, and their approach requires careful consideration of the underlying mathematical structures of revocation tags and tokens. Future work could explore the possibility of converting other group signature schemes into traceable signatures.