Traceable Signatures from Lattices Journal: Journal of Computer Standards and Interfaces
Nam Tran, Khoa Nguyen, Dongxi Liu, Josef Pieprzyk, Willy Susilo · 2025
Read Traceable Signatures from Lattices Journal: Journal of Computer Standards and Interfaces by Nam Tran, Khoa Nguyen, Dongxi Liu, Josef Pieprzyk, Willy Susilo (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2510-24101.txt.
Introduction
Nam Tran and four co-authors build a traceable signature scheme from lattice problems, aiming for safety against quantum computers. Traceable signatures let a user sign without revealing identity, while an opening authority can trace a signature in set cases. All prior schemes rest on number theory or pairings, which quantum machines may break.
Their construction uses lattices instead and comes with a proof of security in the quantum random oracle model. The paper revisits the definition of traceable signatures and shows the lattice version keeps anonymity and tracing power. The result offers a path to keep this privacy tool usable if large quantum computers arrive.
Catalog record
| CREATOR | Nam Tran, Khoa Nguyen, Dongxi Liu, Josef Pieprzyk, Willy Susilo |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 145 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2510-24101
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Traceable Signatures from Lattices Journal: Journal of Computer Standards and Interfaces Nam Tran, Khoa Nguyen, Dongxi Liu, Josef Pieprzyk, Willy Susilo Abstract Traceable signatures (Kiayas et al. , EUROCRYPT’04) is an anonymous digital signature system that extends the tracing power of opening authority in group signatures. There are many known constructions of traceable signatures but all are based on number-theoretical/pairing assumptions. For such reason, they may not be secure in the presence of quantum computers. This work revisits the notion of traceable signatures and presents a lattice-based construction provably secure in the quantum random oracle model (QROM). 1 Introduction In today’s world, balancing privacy with accountability has become a fundamental challenge for designing communication systems. Group signatures, introduced by Chaum and van Heyst [ 1 ] , was an attempt at resolving this problem by allowing users to sign messages anonymously with a group manager who can trace signatures to their original signers. This dual capability makes group signatures particularly valuable in applications requiring privacy protection and accountability mechanisms. Since their introduction, group signatures have evolved drastically with constructions such as [ 2 , 3 , 4 , 5 , 6 ] , offering increasingly practical solutions. However, these schemes rely on number-theoretical assumptions (either RSA-based or Diffie-Hellman in groups equipped with bilinear pairings) and are vulnerable to attacks from quantum computers. This drawback motivated the search for post-quantum candidates, with Gordon et al. [ 7 ] giving the first lattice-based group signature scheme in 2010. Since then, this has been an active research area that has developed many constructions with security and efficiency gradually approaching that of their classical counterparts. Lattice-based constructions are the most dominant among proposals of post-quantum group signatures and remain the most advanced regarding security and efficiency. Although the initial proposal from Gordon et al. [ 7 ] only achieved weak anonymity with signature size linear order in the number of group members, subsequent works by Laguillaumie et al. [ 8 ] and others [ 9 , 10 , 11 ] made significant improvement. They simultaneously reduced the signature size to be logarithmic in group size and achieved anonymity in the strongest sense, where signers’ secrets are exposed, and the adversary can open signatures of its choice. Current state-of-the-art constructions are from [ 12 , 13 ] , with a signature size of a few hundred kilobytes for a group size of roughly one million. Alternatives other than lattices have also been explored, including isogeny-based [ 14 ] , hash-based [ 15 ] , and code-based constructions [ 16 , 17 , 18 ] . The code-based scheme from [ 17 ] achieves full-anonymity and has a logarithmic signature size in the group size. Recently, [ 19 ] proposed a zero-knowledge protocol from the VOLE-in-the-Head framework, which substantially improved upon previous code-based protocols. As an application, they reduced signature size in the scheme from [ 17 ] to roughly half a megabyte for a group size of around a billion. Beyond basic user tracing, incorporating advanced functionalities in group signatures is a related topic that has raised much interest. The need for such features stems from specific privacy and security challenges that the existing means of group signatures may not easily deal with. For example, when the group manager expels some individuals from the group due to misbehavior, it should identify and revoke signatures produced from those. A simple method is to recollect and open every signature, but other users’ anonymity would be affected. The notion of verifier local revocable (VLR) group signatures [ 20 ] deals with such challenge, by offering a membership-revoking mechanism so that signatures remain valid as long as signers are members of the group. There is also the scenario when the group manager is not fully trusted and needs to be responsible for action. Such is addressed by the notion of accountable tracing signatures [ 21 ] . Another interesting functionality is message-dependent opening [ 22 ] , where the group manager can only open signatures on specific messages with the help of another third party (admitter). In the same spirit, many proposals of privacy-preserving signature systems generalize group signatures by enhancing the tracing power of authority while still protecting users’ privacy to a certain extent [ 23 , 24 , 25 ] . This research direction also results in a long line of work extending post-quantum group signatures by incorporating sophisticated and expressive tracing features [ 26 , 27 , 28 , 29 , 24 , 25 ] . This work focuses on traceable signatures, proposed by Kiayias, Tsiounis, and Yung [ 30 ] . In essence, traceable signatures are group signatures but offer more tracing power to the group manager and users. In addition to standard tracing capability, group manager also has a user-specific tracing power that can be widely distributed among the system. Roughly speaking, the group manager possesses information called tracing trapdoor unique to each user. When delegated to sub-openers, the tracing trapdoor helps recognize signatures from the corresponding user while not affecting the privacy of others. In this way, user-specific tracing can be performed concurrently and without recollecting all of the previously issued signatures. In addition, traceable signatures also offer a self-tracing mechanism, allowing a user to claim authorship of previously issued signatures without revealing any sensitive information that may compromise its anonymity in the past or the future. Traceable signatures may find application in anonymous systems where simple tracing is not enough to hold users accountable. For example, in financial transaction systems, there could be situations where a user conducts illegal trading activities. In such cases, the system administrator and other users should be able to invalidate the user’s previous and future transactions. A user-specific tracing method is best for this scenario, which is offered by the means of traceable signatures. Furthermore, a self-tracing capability can allow users to argue that they conducted past transactions faithfully, preventing trading assets from any ownership dispute while maintaining privacy for their other activities. Functionality Construction Post-quantum Assumption and Security Model Verifier local-revocation [ 20 , 28 , 31 , 32 ] Lattice-based + ROM [ 28 , 32 ] Accountable tracing [ 21 , 29 ] Lattice-based + ROM [ 29 ] Message-dependent opening [ 22 , 26 , 33 ] Lattice-based + ROM [ 26 , 33 ] User-specific tracing and self-tracing [ 30 , 34 , 35 ] ✗ Table 1: An overview of some advanced tracing functionalities in group signatures with the corresponding proposals. For constructions from post-quantum assumptions, we list the assumption type and security model in the third column. We remark that for group signatures with user-specific tracing and self-tracing (i.e., traceable signatures), all known constructions are from number-theoretic assumptions. To the best of our knowledge, only [ 36 ] proposed a lattice-based traceable signature scheme. However, we identify a critical flaw which will be explained later. Formalization of Traceable Signatures . Kiayias et al. [ 30 ] defined the syntax and security requirement of traceable signatures, which we refer to as the KTY model. Informally, a traceable signature scheme in a collection of efficient algorithms ( \mathsf{Setup} , \mathsf{Join} , \mathsf{Sign} , \mathsf{Verify} , \mathsf{Open} , \mathsf{Reveal} , \mathsf{Trace} , \mathsf{Claim}