Authors: Wei Wei, Min Luo, Zijian Bao, Cong Peng and Debiao He

Title: Traceable Ring Signatures from Group Actions: Logarithmic, Flexible, and Quantum Resistant

Conference: Selected Areas in Cryptography 2023

Abstract:  Traceable ring signature (TRS) is a variation of ring signature, allowing to expose the user’s identity whenever he signs two different messages under the same tag. The accountable anonymity of TRS makes it widely used in many restrained anonymous applications, e.g., e-voting system, offline coupon service. Traditional TRS schemes are built on number theory and are not resistant to quantum attacks. While numerous post-quantum (traceable) ring signature schemes have been carried out so far, there has been no TRS scheme based on isogenies proposed. We construct an efficient TRS from isogenies that can be instantiated from versatile assumption: including groups of which structure is unknown. The critical technique is to design an OR sigma protocol to generate proofs for multiple tag sets and public-secret key pairs, which provides linkability and traceability for TRS scheme. The signature size can be expressed as O(logN), where N is the ring size. In the real scenario, users can flexibly customize the signature size and signature time according to their own requirements with different instantiation parameters. Moreover, we prove the security of our scheme under the standard random oracle model.