Unlinkable and Strongly Accountable Sanitizable Signatures from Verifiable Ring Signatures

An Unlinkable Sanitizable Signature scheme (USS) allows a sanitizer to modify some parts of a signed message in such away that nobody can link the modified signature to the original one. A Verifiable Ring Signature scheme (VRS) allows the users to sign messages anonymously within a group where a user can prove a posteriori to a verifier that it is the author of a given signature. In this paper, we first revisit the notion of VRS: we improve the proof capabilities of the users, we give a complete security model for VRS and we give an efficient and secure scheme called \(\mathrm {EVeR}\). Our main contribution is \(\mathrm {GUSS}\), a Generic USS based on a VRS scheme and an unforgeable signature scheme. We show that \(\mathrm {GUSS}\) instantiated with \(\mathrm {EVeR}\) and Schnorr’s signature is twice as efficient as the best USS scheme of the literature. Moreover, we propose a stronger definition of accountability: an USS is accountable when the signer can prove whether a signature is sanitized. We formally define the notion of strong accountability where the sanitizer can also prove the origin of a signature. We show that the notion of strong accountability is important in practice. Finally, we prove the security properties of \(\mathrm {GUSS}\) (including strong accountability) and \(\mathrm {EVeR}\) under the Decisional Diffie-Hellman (DDH) assumption in the random oracle model.