Fully-secure and practical sanitizable signatures

Sanitizable signatures have been introduced recently to provide a means for the signer to authorize a censor to modify some parts of the signed message without the help of the original signer. This paper presents the following three contributions. (1) We point out the weaknesses of Brzuska et al.'s (PKC 2009) and Canard et al.'s (CT-RSA 2010) constructions respectively. Namely we show that their constructions are not signer-accountable. (2) We point out the weakness of Brzuska et al.'s security model (PKC 2009) for sanitizable signatures by showing some potential attacks neglected in their original model. (3) We present a stronger security model based on Brzuska et al.'s model and a fully-secure construction based on both Brzuska et al.'s and Canard et al.'s constructions. We must note that our proposed construction is much more practical than prior ones. In detail, the computation costs of signing, sanitizing and verification algorithm are constant and the signature size is constant as well.