Aarhus University Seal / Aarhus Universitets segl

Mark Simkin

Efficient unlinkable sanitizable signatures from signatures with re-randomizable keys

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaperJournal articleResearchpeer-review

  • Nils Fleischhacker, Johns Hopkins University Hospital
  • ,
  • Johannes Krupp, Saarland University
  • ,
  • Giulio Malavolta, Lehrstuhl für Theoretische Chemie/Computer Chemie Centrum, Friedrich-Alexander Universität Erlangen-Nürnberg, Germany.
  • ,
  • Jonas Schneider, Saarland University
  • ,
  • Dominique Schröder, Lehrstuhl für Theoretische Chemie/Computer Chemie Centrum, Friedrich-Alexander Universität Erlangen-Nürnberg, Germany.
  • ,
  • Mark Simkin

A sanitizable signature scheme is a malleable signature scheme where a designated third party has the permission to modify certain parts of the message and adapt the signature accordingly. This primitive was introduced by Ateniese et al. (ESORICS 2005) and Brzuska et al. (PKC 2009) formalized the initially suggested five security properties. In the subsequent year, Brzuska et al. (PKC 2010) introduced a notion called unlinkability where the basic idea is that linking message-signature pairs of the same document should be infeasible. Brzuska et al. formalized this notion and suggested a generic instantiation based on group signatures with a special structure. Unfortunately, the most efficient instantiations of group signatures do not have this property. In this work, we present the first efficient construction of unlinkable sanitizable signatures based on a novel type of signature schemes with re-randomizable keys. This property allows one to re-randomize both the signing and the verification key separately but consistently. Given a signature scheme with re-randomizable keys, we obtain a sanitizable signature scheme by signing the message with a re-randomized key and proving in zero-knowledge that the derived key originates from either the signer or the sanitizer. To obtain an efficient instantiation, we instantiate this generic idea with Schnorr signatures and efficient σ-protocols that we turn into a non-interactive zero-knowledge proof via the Fiat-Shamir transformation. In this work, we present an optimized version that is more efficient than the construction we suggested in the extended abstract of this work at PKC 2016.

Original languageEnglish
JournalIET Information Security
Pages (from-to)166-183
Number of pages18
Publication statusPublished - 1 May 2018

See relations at Aarhus University Citationformats

ID: 143264108