Cryptology ePrint Archive: Report 2015/395

Efficient Unlinkable Sanitizable Signatures from Signatures with Rerandomizable Keys

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

Abstract: Sanitizable signature schemes are a type of malleable signatures where the signer grants a designated third party, called the sanitizer, signing rights in the sense that the sanitizer can modify designated parts 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 one cannot link sanitized message-signature pairs of the same document and gave a generic construction based on group signatures that have a certain structure.

Here, we present the first efficient instantiation of unlinkable sanitizable signatures. Our construction is based on a novel type of signature schemes with rerandomizable keys. Intuitively, this property allows to rerandomize both the signing and the verification key independently but consistently. This allows us to sign the message with a rerandomized 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 the fastest known construction.

Category / Keywords: public-key cryptography / digital signatures, rerandomizable keys

Date: received 27 Apr 2015

Contact author: fleischhacker at cs uni-saarland de

Available format(s): PDF | BibTeX Citation

Version: 20150501:120419 (All versions of this report)

Short URL: ia.cr/2015/395

Discussion forum: Show discussion | Start new discussion