k-Times Full Traceable Ring Signature

International audience—Ring and group signatures allow their members to anonymously sign documents in the name of the group. In ring signatures, members manage the group themselves in an ad-hoc manner while in group signatures, a manager is required. Moreover, k-times traceable group and ring signatures [1] allow anyone to publicly trace two signatures from a same user if he exceeds the a priori authorized number of signatures. In [2], Canard et al. give a 1-time traceable ring signature where each member can only generate one anonymous signature. Hence, it is possible to trace any two signatures from the same user. Some other works generalize it to the k-times case, but the traceability only concerns two signatures. In this paper, we define the notion of k-times full traceable ring signature (k-FTRS) such that all signatures produced by the same user are traceable if and only if he produces more than k signatures. We construct a k-FTRS called Ktrace. We extend existing formal security models of k-times linkable signatures to prove the security of Ktrace in the random oracle model. Our primitive k-FTRS can be used to construct a k-times veto scheme or a proxy e-voting scheme that prevents denial-of-service caused by cheating users