Most aggregate signature schemes are relying on pairings, but high computational and storage costs of pairings limit the feasibility of those schemes in practice. Zhao proposed the first pairing-free aggregate signature scheme (AsiaCCS 2019). However, the security of Zhao's scheme is based on the hardness of a newly introduced non-standard computational problem. The recent impossibility results of Drijvers et al. (IEEE S&P 2019) on two-round pairing-free multi-signature schemes whose security based on the standard discrete logarithm (DL) problem have strengthened the view that constructing a pairing-free aggregate signature scheme which is proven secure based on standard problems such as DL problem is indeed a challenging open problem. In this paper, we offer a novel solution to this open problem. We introduce a new paradigm of aggregate signatures, i.e., aggregate signatures with an additional pre-communication stage. In the pre-communication stage, each signer interacts with the aggregator to agree on a specific random value before deciding messages to be signed. We also discover that the impossibility results of Drijvers et al. take effect if the adversary can decide the whole randomness part of any individual signature. Based on the new paradigm and our discovery of the applicability of the impossibility result, we propose a pairing-free aggregate signature scheme such that any individual signature includes a random nonce which can be freely generated by the signer. We prove the security of our scheme based on the hardness of the standard DL problem. As a trade-off, in contrast to the plain public-key model, which Zhao's scheme uses, we employ a more restricted key setup model, i.e., the knowledge of secret-key model.

The existing discrete-logarithm-based two-round multi-signature schemes without using the idealized model, i.e., the Algebraic Group Model (AGM), have quite large reduction loss. This means that an implementation of these schemes requires an elliptic curve (EC) with a very large order for the standard 128-bit security when we consider concrete security. Indeed, the existing standardized ECs have orders too small to ensure 128-bit security of such schemes. Recently, Pan and Wagner proposed two two-round schemes based on the Decisional Diffie-Hellman (DDH) assumption (EUROCRYPT 2023). For 128-bit security in concrete security, the first scheme can use the NIST-standardized EC P-256 and the second can use P-384. However, with these parameter choices, they do not improve the signature size and the communication complexity over the existing non-tight schemes. Therefore, there is no two-round scheme that (i) can use a standardized EC for 128-bit security and (ii) has high efficiency. In this paper, we construct a two-round multi-signature scheme achieving both of them from the DDH assumption. We prove that an EC with at least a 321-bit order is sufficient for our scheme to ensure 128-bit security. Thus, we can use the NIST-standardized EC P-384 for 128-bit security. Moreover, the signature size and the communication complexity per one signer of our proposed scheme under P-384 are 1152 bits and 1535 bits, respectively. These are most efficient among the existing two-round schemes without using the AGM including Pan-Wagner’s schemes and non-tight schemes which do not use the AGM. Our experiment on an ordinary machine shows that for signing and verification, each can be completed in about 65 ms under 100 signers. This shows that our scheme has sufficiently reasonable running time in practice.