Contributions to Ring Signatures

<p dir="ltr">Cryptography is fundamental to securing electronic communications, ensuring privacy, integrity, and authenticity. Among its core tools, digital signatures enable individuals to sign electronic documents and messages securely, verifying the signer’s identity, preserving message integrity, and ensuring non-repudiation. These properties make digital signatures indispensable for applications such as legal document authentication, software distribution, and secure email. However, in many real-world scenarios, revealing the signer’s identity is undesirable. For instance, whistleblowers may need to report sensitive information without fear of retaliation; businesses may conduct confidential transactions while protecting the identities of their participants; and electronic voting systems may require voter anonymity while ensuring election integrity. In such cases, traditional digital signatures are insufficient because they explicitly link a signature to a known individual.</p><p dir="ltr">Ring signatures allow any member of a predefined group to sign a message anonymously. While the signature confirms the authenticity and integrity of the message, the actual signer remains untraceable within the group. By contrast, group signatures also provide anonymous group signing but enable a designated manager to trace and reveal the signer’s identity when necessary. The strong anonymity property of ring signatures makes them particularly valuable for privacy-preserving applications. Nevertheless, several challenges remain, including improving efficiency, strengthening security, and ensuring scalability in practical implementations.</p><p dir="ltr">This thesis presents significant advancements in ring signatures, focusing on improving their functionality, efficiency, and security under practical cryptographic assumptions. The main contributions are as follows:</p><p dir="ltr">• The first contribution proposes a novel approach to constructing Traceable Ring Signatures (TRS) that is proved secure in a strong security proof model. Originally proposed by Fujisaki and Suzuki at PKC 2007, TRS enables public traceability of a user’s identity if they sign twice on different messages with the same tag. This property has practical applications in areas such as e-coupons, e-voting, and blockchain technology. Existing schemes typically rely on the (quantum) random oracle or common reference string models, which introduce impractical or inefficient assumptions. This thesis presents the first generic construction of traceable ring signatures that avoids a trusted setup and the random oracle heuristic, relying instead on standard assumptions. It achieves a signature size that scales logarithmically with the number of ring members.</p><p dir="ltr">• The second contribution introduces Threshold Ring Signatures with Accountability (AThRS). While traditional threshold ring signatures allow multiple signers to collaboratively sign a message without revealing individual identities, AThRS balances anonymity and accountability. Specifically, it enables a designated opener to disclose the signers’ identities when necessary, provided that the signers give their consent before signing. Additionally, AThRS supports a verifiable opening mechanism, ensuring that the opener cannot falsely attribute a signature to any signer. This thesis presents a generic construction of AThRS using standard cryptographic primitives. It is secure in the plain model and achieves logarithmic signature size.</p><p dir="ltr">• The third contribution presents a novel generic construction of Accountable Ring Signatures (ARS) in a strong security proof model. ARS bridges the conceptual and functional gap between traditional ring signatures and group signatures. Specifically, ARS preserves signer anonymity within a predefined set (as in ring signatures) while allowing a designated opener to reveal the actual signer when necessary, ensuring accountability. Previous ARS constructions have relied on trusted models or were secure only in the random oracle model. This thesis presents the first generic construction of ARS schemes that are secure in the plain model, achieve a logarithmic signature size, and eliminate the need for heuristic or trusted setup assumptions.</p><p dir="ltr">• Lastly, we introduce the first (Linkable) Ring Signatures based on the Lattice Isomorphism Problem (LIP). Recognized as a promising post-quantum cryptographic problem, LIP is believed to be hard to solve even with the advent of quantum computers, making it an attractive basis for secure cryptographic constructions in a future where quantum attacks are a concern. The importance of LIP lies in its connection to lattice-based cryptography, which offers strong security guarantees under widely studied hardness assumptions. By leveraging the presumed difficulty of LIP, our proposed (linkable) ring signature schemes inherit post-quantum security, ensuring that they remain robust against both classical and quantum adversaries. Our schemes feature logarithmic signature sizes relative to the number of ring users, significantly reducing the signature size compared to other schemes when the number of users is large.</p>