Design And Analysis Of Aggregate Signature Scheme Resistant To Collusion Attack

To demonstrate the authenticity of a digital message or document, digital signature schemes are applied in modern cryptography. In many situations, there is the need to transmit and verify large quantities of signatures. Aggregate signature is a cryptographic technique that is employed to transform many signatures generated by many signers on many messages into one single aggregate signature, so that the communication cost for transmitting many message-signature pairs can be greatly reduced. Hence, aggregate signature is a promising tool in improving the efficiency of these applications. With regard to security, the validity of an aggregate signature should ensure the validity of every single signature involved in the aggregation. As a result, the verifier of the aggregate signature is convinced that every signer did sign the corresponding message. However, in some existing aggregate signature schemes, the validity of an aggregate signature may not guarantee the validity of all single signatures used to generate the aggregate signature.In this thesis, we mainly concentrate on certificateless aggregate signature (CLAS) scheme and identity-based aggregate signature (IBAS) scheme. In identity-based setting, we firstly take a previously proposed identity-based aggregate signature (IBAS) scheme as an example to illustrate a drawback in its security. The potential threat in applying this system is that it is possible for some signers to output invalid single signatures which could be aggregated into a valid aggregate signature by colluding together. Because the security model in previous scheme dose not take this particular attack into consideration and restricts the adversary’s power to launch this attack. Then we redefine the security model of IBAS schemes and present a novel construction, In the newly proposed scheme, an extra hash function is applied in the aggregation phase to guarantee that the aggregate signature is valid if and only if every single signature involved in the aggregation is valid. Unlike previous scheme, to aggregate single signatures into an aggregate signature, the aggregator needs to take all these single signatures and the verifier’s public key as input. The existential unforgeability of aggregate signature is achieved through the collision resistance property of hash function. In addition, based on some classical hardness assumptions, namely the computational Diffie-Hellman (CDH) assumption and the hash function we apply is collision resilient, we prove that our construction satisfies the security requirement in the redefined security model. Another advantage of our scheme is that the signers do not have to negotiate a common random string or synchronize a clock before signing a message, i.e. every signer could sign his message individually.While in the certificateless setting, we at first analyze the recently proposed CLAS scheme by Cheng et al. As for the underlying certificateless signature (CLS) scheme, there is a slight weakness that makes it cannot withstand "malicious but passive" key generation center (KGC) attack. Some improvements are presented to overcome this problem. Then, we give a new insight into the notion and security model of CLAS schemes. Similar to the identity-based setting, we argue that the aggregation algorithm of CLAS scheme should also provide the guarantee that the validity of aggregate signature is equivalent to the validities of all the single signatures. Due to this reason, we demonstrate that the previous construction does not satisfy the security requirement as the security model does not fully address the adversary’s power either that they might collude together. Consequently, we redefine the security model of CLAS schemes considering collusion attack. In this security model, the adversary is able to hold all the signers’private signing keys and his goal is to forge invalid single signatures that could be aggregated into valid aggregate signature. Based on these results, we finally put forward a novel construction of CLAS scheme together with a formal proof that this scheme is secure under the redefined security model. We modify the aggregation algorithm of the CLAS scheme by using an extra hash function. The aggregator has to take all the single signatures and the public key of the verifier selected in advance as inputs and the only way to output valid aggregate signature is from all the valid single signatures.In both the identity-based and certificateless settings, our aggregate signature schemes are resistant to collusion attack, i.e. the adversary cannot forge invalid single signatures that could be aggregated into valid aggregate signature even if he controls all the signers’private signing keys. Compared to the traditional way of transmitting and verifying all the single signatures one by one, the length of the aggregate signature in our scheme is almost half as the single signatures and the verification cost of the aggregate signature is also lower than the single signatures. Specifically, verifying all the single signatures needs extra n pairing operations than verifying the aggregate signature (suppose the aggregate signature is aggregated from n single signatures). And in the identity-based aggregate signature scheme, verifying the single signatures also takes 2n more hash operations than verifying the aggregate signature.