  A redactable signature scheme allows removing parts of a signed message
without invalidating the signature. Currently, the need to prove the validity
of digital documents issued by governments and enterprises is increasing.
However, when disclosing documents, governments and enterprises must remove
privacy information concerning individuals. A redactable signature scheme is
useful for such a situation. In this paper, we introduce the new notion of the
t-out-of-n redactable signature scheme. This scheme has a signer, n redactors,
a combiner, and a verifier. The signer designates n redactors and a combiner in
advance and generates a signature of a message M. Each redactor decides parts
that he or she wants to remove from the message and generates a piece of
redaction information. The combiner collects pieces of redaction information
from all redactors, extracts parts of the message that more than t redactors
want to remove, and generate a redacted message. We consider the one-time
redaction model which allows redacting signatures generated by the signer only
once. We formalize the one-time redaction t-out-of-n redactable signature
scheme, define security, and give a construction using the pairing based
aggregate signature scheme in the random oracle model.
