A Secure Ordered Multisignature without Random Oracles

Ordered multisignature scheme is a signature scheme to guarantee both validity of an electronic document and its signing order. Although the security of most of such schemes has been proven in the random oracle model, the difficulty of implementation of the random oracle implies that the security should be proven without random oracles, i.e. in the standard model. A straightforward way to construct such schemes in the standard model is to apply an aggregate signature scheme by Ahn et al. and an aggregate signature scheme by Lu et al., both of which are based on CDH problem, but these schemes are inefficient in the sense that its computational cost of pairing computation and the size of public keys depend upon the length of (a hash value of) the message. Therefore, in this paper, we propose a CDH-based ordered multisignature scheme whose computational cost for pairing computation and the size of public key are independent of the length of (a hash value of) the message. We also point out a bug of the scheme by Boldyreva et al., and analyze the security of our scheme under a moderate attack model along with fixing the bug.