Miyaji Laboratory

In network communication, ensuring data authenticity and sender authentication is crucial. One of the technologies that achieves this is digital signatures. Multi-signatures, an extension of digital signatures, allow multiple signers to generate a single signature for a shared message, reducing signature length compared to individual signatures. Due to this feature, multi-signatures are widely used in collabora tive editing environments and blockchain. Various multi-signature schemes have been proposed, among which Boneh et al.'s scheme is notable for its concise structure and short signature length, achieved through bilinear mappings. However, multi-signatures require the message to be fixed before signing. In collaborative editing on cloud platforms and approval workflows, modifications to the message or the addition of signers may be necessary. Additionally, in approval workflows, verifying the correct signing order is essential. To address these challenges, Mitomi and Miyaji proposed Message Flexibility (MF), Order Flexibility (OF), and Order Verifiability (OV). These properties eliminate the need to fix the message before signing, allowing modifications and signer additions even during the signing process. Fur thermore, when signers must follow a specific order, the signing order can be verified. However, their multi-signature scheme has a limitation: the signature length depends on the number of signers. Mean while, multi-signature schemes are also subject to attacks. In particular, the Rogue-Key Attack (RKA) allows an attacker to forge a multi-signature for any message using only public information from signers. Almost all early multi-signature schemes are vulnerable to RKA. To mitigate this, countermeasures pro posed by Thomas and Scott, as well as Boneh et al., have been widely adopted in many multi-signature schemes. This study focuses on Boneh et al.'s scheme and extends it by incorporating MF functionality. As a result, we address the limitations of Mitomi and Miyaji's scheme and propose a new scheme with shorter signatures and MF functionality. Furthermore, to clarify the use cases of OF, we categorize it into two types: Predetermined Order Flexibility (POF), where signers and their order are determined before signing, and Arbitrary Order Flexibility (AOF), where the signing order is decided during signing. We propose a multi-signature scheme that supports not only MF but also POF with OV and AOF with OV. Additionally, we demonstrate that the proposed scheme achieves signature length, security, and resistance to RKA comparable to existing multi-signature schemes.