Paper 2022/1293

Improving the Efficiency of Report and Trace Ring Signatures

Xavier Bultel, INSA Centre Val de Loire
Ashley Fraser, University of Surrey
Elizabeth A. Quaglia, Royal Holloway University of London

Ring signatures allow signers to produce verifiable signatures and remain anonymous within a set of signers (i.e., the ring) while doing so. They are well-suited to protocols that target anonymity as a primary goal, for example, anonymous cryptocurrencies. However, standard ring signatures do not ensure that signers are held accountable if they act maliciously. Fraser and Quaglia (CANS'21) introduced a ring signature variant that they called report and trace ring signatures which balances the anonymity guarantee of standard ring signatures with the need to hold signers accountable. In particular, report and trace ring signatures introduce a reporting system whereby ring members can report malicious message/signature pairs. A designated tracer can then revoke the signer's anonymity if, and only if, a ring member submits a report to the tracer. Fraser and Quaglia present a generic construction of a report and trace ring signature scheme and outline an instantiation for which it is claimed that the complexity of signing is linear in the size of the ring $|R|$. In this paper, we introduce a new instantiation of Fraser and Quaglia's generic report and trace ring signature construction. Our instantiation uses a pairing-based variant of ElGamal that we define. We demonstrate that our instantiation is more efficient. In fact, we highlight that the efficiency of Fraser and Quaglia's instantiation omits a scaling factor of $\lambda$ where $\lambda$ is a security parameter. As such, the complexity of signing for their instantiation grows linearly in $\lambda \cdot |R|$. Our instantiation, on the other hand, achieves signing complexity linear in $|R|$. We also introduce a new pairing-free report and trace ring signature construction reaching a similar signing complexity. Whilst this construction requires some additional group exponentiations, it can be instantiated over any prime order group for which the Decisional Diffie-Hellman assumption holds.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. 24th International Symposium on Stabilization, Safety, and Security of Distributed Systems
Ring Signature
Contact author(s)
xavier bultel @ insa-cvl fr
2022-09-29: approved
2022-09-28: received
See all versions
Short URL
Creative Commons Attribution


      author = {Xavier Bultel and Ashley Fraser and Elizabeth A. Quaglia},
      title = {Improving the Efficiency of Report and Trace Ring Signatures},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1293},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.