Certificateless aggregate signature scheme secure against fully chosen-key attacks

Abstract

Certificateless aggregate signature (CLAS) schemes enjoy the benefits of both certificateless cryptography and aggregate signature features. Specifically, it not only simplifies the certificate management without introducing the key escrow problem but also transforms many signatures into one aggregate signature to save communication and computation cost.

CLAS is a powerful cryptographic tool, yet its security should be thoroughly analyzed before being implemented. In this paper, we give a new insight into the security of CLAS schemes. We introduce a potential and realistic attack called fully chosen-key attacks that has not been considered in the traditional security models and define the security model against fully chosen-key attacks. In contrast to the traditional models, the adversary is allowed to hold all the signers’ private keys and its goal is not to forge an aggregate signature but to output invalid single signatures that can be aggregated into a valid aggregate signature. We find there is no CLAS scheme secure in traditional security models that is secure against fully chosen-key attacks and then demonstrate how to reinforce the security of an existing scheme to withstand such an attack.

Introduction

Certificateless cryptography [1] was introduced by Riyami and Paterson to deal with the complicated certificate management problem in the traditional Public-Key Infrastructure (PKI) setting without bringing the key-escrow problem. Aggregate signature [3] can be employed to transform many signatures into one aggregate signature. The motivation of the aggregate signature technique is to reduce the communication and computation costs, where only the aggregate signature is transmitted and verified instead of all the single signatures involved in the aggregation. In situations where a large number of signatures are required to be verified, such as vehicular networks [6], [11], audit log of a computer system [13], auditing scheme with group users [7], and Secure Border Gateway Protocol (SBGP) [24], aggregate signature is a powerful tool to achieve efficiency improvement.

Certificateless aggregate signature (CLAS) schemes enjoy the advantages of both certificateless cryptography and aggregate signature features. It has been found that various applications, not limited to the aforementioned ones, since it was first introduced in [8]. For example, Cloud Storage is gaining its popularity due to low hardware cost, large storage volume, and easy access control. On the other hand, the stability of the storage service is the main security issue that has always been prioritized by users. Cloud auditing is a cryptographic solution for this purpose and in particular, CLAS is a suitable technique to improve the efficiency of the cloud auditing process.

The main entities in a Cloud Storage platform implementing a certificateless cryptographic scheme include the Key Generation Center (KGC), cloud server, Third-Party Auditor (TPA), and the users. During an auditing process, the cloud server computes the response to the challenge from the TPA. Since there are many users in the system, the TPA can send multiple challenges on behalf of multiple users to the cloud server. In a straightforward auditing process, the cloud server computes the corresponding responses and returns them to the TPA. Then, the TPA verifies all the responses one by one. If the cloud server aggregates the responses, both the communication and computation costs of transmitting and verifying the responses can be greatly saved. CLAS technique is suitable for many auditing schemes.

The notion of certificateless aggregate signature (CLAS) schemes was put forth in [8] and many practical constructions [6], [9], [10], [14], [15], [16], [18], [23], [25] are available in the literature to date. In certificateless cryptography, two types of adversaries, namely type I adversary and type II adversary are considered. Furthermore, Huang et al. [12] classified each type of adversary into three kinds; namely normal adversary, strong adversary, and super adversary. Au et al. [2] considered a more powerful KGC (type II) adversary called Malicious-But-Passive KGC (malicious KGC for short). A summary of these security notions can be found in [21].

Recently, Xiong et al. put forward a CLAS scheme [24] with constant pairing computations. Later, cryptanalyses of this construction have been presented [5], [10], [25]. Cheng et al. [5] showed that the single signature of the scheme in [24] does not achieve unforgeability against Honest-But-Curious KGC adversary and proposed an improved scheme to withstand malicious KGC adversary. The security model of CLAS schemes was formalized by Zhang et al. in [28] and has been widely considered for the security model of subsequent scheme constructions and security analyses [4], [5], [10], [19], [20], [22], [25], [26], [27]. The model extends the definition of the seminal work of aggregate signature by Boneh et al. [3] to the certificateless cryptography setting. Although the security model guarantees that the adversary cannot forge an aggregate signature on behalf of all the signers, if it does not hold all the signers’ private keys, we show in this paper that this does not capture all potential threats in practical applications.

The security considered for a signature scheme is unforgeability. Specifically, it guarantees that an adversary without accessing the user’s private key cannot forge a signature on behalf of the user. As for the aggregate signature setting, n signatures signed by n users are aggregated into one aggregate signature. A straightforward extension of the security to the aggregate signature setting is the unforgeability of the aggregate signature. To be more precise, an adversary without accessing all the n users’ private keys cannot forge an aggregate signature on behalf of the users. As a result, the adversary is allowed to adaptively hold at most $n-1$ users’ private keys and its goal is to forge a valid aggregate signature on behalf of the n users. This is the security model considered in the seminal work of aggregate signature [3], which is referred to as the “chosen-key” security model. The existential unforgeability against chosen-key attacks and chosen-message attacks has become the standard security notion of aggregate signature schemes. However, as we shall show in this work, this security does not capture all potential attacks in practical applications.

Fully chosen-key attacks. The motivation of the aggregate signature technique is to improve the efficiency of transmitting and verifying a large number of signatures. In an aggregate signature scheme, only the aggregate signature instead of all single signatures involved in the aggregation is transmitted and verified. The verifier wants to check the validities of all single signatures by verifying the aggregate signature. To convince the verifier, the aggregate signature scheme should provide a guarantee that the validity of the aggregate signature is equivalent to the validities of all the single signatures. In this paper, we refer to it as the equivalent validity.

A secure aggregate signature scheme should achieve equivalent validity not only unforgeability. In traditional security models against chosen-key attacks, the adversary holds at most $n-1$ private keys amongst n users. However, what if the adversary holds all the users’ private keys and its goal is not to forge an aggregate signature but to break the equivalent validity. For example, two dishonest users work together (of course they hold both their private keys) to cheat the verifier. They output two invalid single signatures that are aggregated into a valid aggregate signature. Note that this is a practical attack which breaks the equivalent validity of the aggregate signature scheme. On one hand, the verifier believes that the two single signatures are valid after verifying the aggregate signature. On the other hand, the single signatures are invalid and the two dishonest users can deny that they have signed the signatures. In other words, the equivalent validity should be guaranteed no matter whether the adversary holds all the users’ private keys or not. In this paper, we allow the adversary to hold all the users’ private keys and call it fully chosen-key attacks in contrast to the traditional security models.

To sum up, a secure aggregate signature should satisfy security requirements in two aspects. Namely, the existential unforgeability of single signatures against chosen-message attacks and equivalent validity of an aggregate signature against fully chosen-key attacks. In particular, for a certificateless aggregate signature (CLAS) scheme, the single signatures should be existentially unforgeable against both type I and type II adversaries. Since the fully chosen-key attacks allow the adversary to hold all the users’ private keys, there is no need to distinguish the two types of adversaries in the security model of equivalent validity against fully chosen-key attacks.

In this paper, we take an insight into the security of certificateless aggregate signature (CLAS) schemes. The contributions of this work are three-fold and summarized as follows.

• We consider the equivalent security against fully chosen-key attacks which is not captured in the traditional security models of CLAS schemes and propose the formal definition and security model.

• A scheme secure in the traditional security model is not necessarily secure against fully chosen-key attacks. We demonstrate how to reinforce the security to withstand fully chosen-key attacks taking the scheme in [5] as an example. The transformation is general, where a collision-resistant hash function is applied.

• In addition, we give re-formalized security proofs of the single signatures in the proposed scheme, which include the existential unforgeability against chosen-message attacks by a strong type I adversary and a super type II (Malicious-But-Passive KGC) adversary.

The rest of this paper is organized as follows.

We begin with presenting the definition and security models of certificateless aggregate signature (CLAS) schemes in Section 2. A review of the scheme in [5] is given in Section 3. In Section 4, we propose an improved scheme, secure in the security models defined in this paper. The efficiency and experimental analyses will be provided in Section 5. Finally, we conclude this paper in Section 6.