Paper 2015/395

Efficient Unlinkable Sanitizable Signatures from Signatures with Re-Randomizable Keys

Nils Fleischhacker, Johannes Krupp, Giulio Malavolta, Jonas Schneider, Dominique Schröder, and Mark Simkin


In a sanitizable signature scheme the signer allows a designated third party, called the sanitizer, to modify certain parts of the message and adapt the signature accordingly. Ateniese et al. (ESORICS 2005) introduced this primitive and proposed five security properties which were formalized by Brzuska et al.~(PKC 2009). Subsequently, Brzuska et al. (PKC 2010) suggested an additional security notion, called unlinkability which says that one cannot link sanitized message-signature pairs of the same document. Moreover, the authors gave a generic construction based on group signatures that have a certain structure. However, the special structure required from the group signature scheme only allows for inefficient instantiations. Here, we present the first efficient instantiation of unlinkable sanitizable signatures. Our construction is based on a novel type of signature schemes with re-randomizable keys. Intuitively, this property allows to re-randomize both the signing and the verification key separately but consistently. This allows us to sign the message with a re-randomized key and to prove in zero-knowledge that the derived key originates from either the signer or the sanitizer. We instantiate this generic idea with Schnorr signatures and efficient $\Sigma$-protocols, which we convert into non-interactive zero-knowledge proofs via the Fiat-Shamir transformation. Our construction is at least one order of magnitude faster than instantiating the generic scheme of Brzuska et al. with the most efficient group signature schemes.

Available format(s)
Public-key cryptography
Publication info
A minor revision of an IACR publication in PKC 2016
digital signaturesrerandomizable keys
Contact author(s)
fleischhacker @ cs uni-saarland de
2016-02-11: revised
2015-05-01: received
See all versions
Short URL
Creative Commons Attribution


      author = {Nils Fleischhacker and Johannes Krupp and Giulio Malavolta and Jonas Schneider and Dominique Schröder and Mark Simkin},
      title = {Efficient Unlinkable Sanitizable Signatures from Signatures with Re-Randomizable Keys},
      howpublished = {Cryptology ePrint Archive, Paper 2015/395},
      year = {2015},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.