Multisignature schemes enable us to integrate multiple signatures into a single short signature. In 2001, Mitomi and Miyaji proposed a general model of multisignatures, in which signed messages are flexible and the signing order is verifiable and flexible. Several schemes that satisfy these properties have been proposed, but to the best of our knowledge, their verifiable orders are limited to only sequential structures unlike some order-verifiable (but not message-flexible) multisignatures. We define a signing structure as a labeled tree, which can represent any natural signing order including series-parallel graphs, and formalize a general model of multisignatures that makes good use of our structure. We present a security model for such signatures, give the construction based on the general aggregate signature developed by Boneh et al., and provide a security proof in the random oracle model.

We present a new notion of public-key encryption, called multi-divisible on-line/off-line encryptions, in which partial ciphertexts can be computed and made publicly available for the recipients before the recipients' public key and/or the plaintexts are determined. We formalize its syntax and define several security notions with regard to the level of divisibility, the number of users, and the number of encryption (challenge) queries per user. Furthermore, we show implications and separations between these security notions and classify them into three categories. We also present concrete multi-divisible on-line/off-line encryption schemes. The schemes allow the computationally-restricted and/or bandwidth-restricted devices to transmit ciphertexts with low computational overhead and/or low-bandwidth network.