Tightly Secure Aggregate Signature with Pre-Communication

Aggregate signatures without the bilinear map is a challenging and important problem in aspects of both practical and theoretical cryptology. In order to construct an aggregate signature which does not use the bilinear map, it is general to restrict some functionality of aggregate signatures or to employ strong cryptographic assumptions. The aggregate signature with the pre-communication (ASwPC) is one of the variants of aggregate signatures to achieve the security from a standard cryptographic assumption without the bilinear map. The ASwPC requires signers to interact with each other to share a temporary randomness before they determine their messages to be signed. After the pre-communication, each signer can start the signing process individually. An instantiation of ASwPC is given based on the discrete logarithm (DL) assumption, and its security is proven in the random oracle and the knowledge of secret key (KOSK) model via a loose security reduction. In this paper, we aim to construct a new ASwPC scheme whose security is proven via a tight security reduction. We employ the DDH assumption rather than the DL assumption. The combination of the property of the decisional assumption and that of the KOSK model enables us to apply the lossy key technique even in the case of ASwPC. Then we can prove the security of our scheme with a tight security reduction.