Efficient Unlinkable Sanitizable Signatures from Signatures with Re-randomizable Keys
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 secu
- PDF / 578,550 Bytes
- 30 Pages / 439.37 x 666.142 pts Page_size
- 29 Downloads / 221 Views
stract. 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 Σ-protocols, which we convert into noninteractive 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.
1
Introduction
Sanitizable signature schemes were introduced by Ateniese et al. [1] and similar primitives were concurrently proposed by Steinfeld et al. [42], by Miyazaki et al. [36], and by Johnson et al. [34]. The basic idea of this primitive is that the signer specifies parts of a (signed) message such that a dedicated third party, called the sanitizer, can change the message and adapt the signature accordingly. Sanitizable signatures have numerous applications, such as the anonymization of medical data, replacing commercials in authenticated media streams, or updates of reliable routing information [1]. After the first introduction of sanitizable signatures in [1], the desired security properties were later formalized by c International Association for Cryptologic Research 2016 C.-M. Cheng et al. (Eds.): PKC 2016, Part I, LNCS 9614, pp. 301–330, 2016. DOI: 10.1007/978-3-662-49384-7 12
302
N. Fleischhacker et al.
Brzuska et al. [11]. At PKC 2010, Brzuska et al. [12] identified an important missing property called unlinkability. Loosely speaking, this notion ensures that one cannot link sanitized message-signature pairs of the same document. This property is essential in applications like the sanitization of medical records because it prevents the attacker from combining information of several sanitized versions of a document in order to reconstruct (parts of) the original document. The authors also showed that unlinkable sanitizable signatures can be constructed from group signatures [4] having th
Data Loading...
