Message and Order Flexible Pairing based Multisignature

Multisignature is a scheme in which multiple signers sign a common message. Despite involving various signers, it generates a signature of a length comparable to that of a single signer and allows verifiers to determine who signed the message. Mitomi and Miyaji proposed a Message Flexible multisignature scheme suitable for collaborative editing environments. This scheme provides for the addition and modification of messages during the signature generation process without fixing the signed message in advance. However, Mitomi and Miyaji’s method has the drawback that the signature length increases with the number of signers. In response, Hayashida and Miyaji proposed a message-flexible multisignature scheme with a fixed signature length. Nevertheless, their proposed method lacks flexibility compared to Mitomi and Miyaji’s method, as it does not allow the addition of signers. Therefore, this study aims to improve Hayashida and Miyaji’s method by proposing a message and order-flexible multisignature scheme that enables the addition of signers while maintaining a fixed signature length.