Secure One-to-Group Communications Escrow-Free ID-Based Asymmetric Group Key Agreement

Abstract

Group key agreement (GKA) is widely employed for secure group communications. Yet there is an increasing demand for secure one-to-group communications in distributed computing applications. Asymmetric group key agreement (AGKA) is a handy tool to answer this need. In AGKA, a group of members can establish a group public key while each member has a different secret key. Any sender can encrypt under this group key such that any of the members who hold the secret key can decrypt. This paper proposes an identity-based AGKA protocol which is secure against active attackers, with an emphasis on optimal round efficiency, sender dynamics, and escrow freeness. The last feature offers security of the previously established ciphertexts even when either all the involved participants or the key generation center of the identity-based cryptosystem are compromised. The proposed protocol is shown to be secure under the $k$-Bilinear Diffie-Hellman exponent assumption in the random oracle model. Regarding performance, our protocol is comparable to the state-of-the-art AGKA protocols.

1 Introduction

In ubiquitous computing applications such as wireless mesh networks and mobile ad hoc networks, there is a need to efficiently and securely broadcast to a remote cooperative group. A popular approach to secure group communications is to exploit group key agreement (GKA) [5]. Conventional GKA protocols allow a group of members to interact over an open network to establish a common secret key; thereafter, the group members can securely exchange messages using this shared key. Thus, conventional GKA protocols are sender restricted in the sense that, when a sender wants to send a secret message to a group of receivers, the sender has to first join the receivers to form a group and then run a GKA protocol. To see the limitations, let us consider the following scenarios.

Scenario 1. A group of users in different time zones would like to discuss on some sensitive topics over an untrusted medium, e.g., via a social network service provider.

Scenario 2. One or more soldiers may want to securely report to a group of tactical units.

Up to now, most existing efficient GKA protocols need at least two rounds [12, 19]. In Scenario 1, all the users have to stay online to finish the protocol before they can wait for encrypted contents, which is a prohibitive way for users in different time zones. In Scenario 2, the same key will be derived from the GKA protocol for a soldier and the tactical units. The compromise of any one soldier will compromise the secrecy of the communication among the tactical units as well. This is also prohibitive since a soldier is conceivably under a poor communication environment.

Motivated by above scenarios, Wu et al. [21] introduced the notion of asymmetric group key agreement (AGKA) and proposed a concrete one-round AGKA protocol. Unlike regular GKA, AGKA allows the members to negotiate a common group encryption key while holding different (group) decryption keys. The group encryption key is publicly accessible and enables any sender to securely encrypt to the group members. The decryption key, which is different from the long-term private key of the user, can be used to decrypt every ciphertexts encrypted under the group encryption key.

The above AGKA protocol, and the subsequent improvements [22, 23], are based on traditional public-key infrastructure (PKI). The idea of identity-based cryptosystem (IBC) proposed by Shamir [18] eliminates complicated certificate management in PKI, with the help of a trusted key generation centre (KGC) for creating the long-term identity-based secret keys for the group members. Identity-based AGKA (IBAGKA) protocols have been proposed [26, 27]. Using these identity-based secret keys with AGKA, the members can securely establish a secure broadcast channel among them, without relying on PKI.

The original AGKA notion and the instantiated protocol are only secure against passive attackers who just eavesdrop the open communications. This is not sufficient against realistic attackers who may fully control the open networks and launch more powerful active attacks such as member impersonation, communication tampering, replay of early protocol transcripts, etc. To counter this kind of attackers, an additional identity-based signature scheme is used on top of the IBAGKA protocol [26, 27].

The authenticated AGKA protocol in [26, 27] achieves partial forward secrecy. That is, if only one or some specific group members’ long-term keys are compromised, the secrets exchanged before the compromise stay unknown to the attacker. However, if all the group members’ long-term keys are leaked, then the previously established secrets will be exposed to the attacker and the protocol will no longer be secure. Obviously, since the long-term keys for the group members are generated by the KGC, the KGC can always read the secrets. This is known as the key escrow problem. Further, in practice, we do not know which members might be compromised after the protocol is deployed and, in the worst case, all the members and even the KGC might be compromised. These observations motivate us to investigate authenticated AGKA protocols with stronger active security.

1.1 Our Contributions

This paper contributes to the study of authenticated AGKA in the IBC setting, in the following aspects.

We first formalize the notion of IBAAGKA without escrow. Our notion captures the typical active security properties of secrecy and known-key security [26, 27] derived from their analogs in conventional authenticated GKA protocols. The former means that only the group members can read the message exchanged after the AGKA protocol is executed. The latter means that an attacker who knows the decryption keys of previous sessions cannot compute subsequent group decryption keys. Furthermore, our notion also captures escrow freeness [7] (just like the standard perfect forward secrecy [1, 2]) by allowing an attacker to corrupt the KGC. True, a KGC can always generate the long-term identity-based secret keys of any user. However, even such an attacker cannot read any secret messages exchanged before the corruption.

To motivate our design of authenticated AGKA protocol, we first propose and realize our new notion of strongly unforgeable stateful identity-based batch multi-signatures (IBBMS). Borrowing its design, we propose an IBAAGKA protocol without escrow. The protocol is shown to be secure against active attacks in our strengthened model. The proof relies on the $k$-Bilinear Diffie-Hellman Exponent assumption (which is widely used in recent cryptographic constructions) and the strong unforgeability of our stateful IBBMS. The protocol needs only one round to enable a group of members to establish a common encryption and their respective decryption keys. A detailed analysis shows that the complexity in computation and communication of our authenticated AGKA protocol is comparable to that of up-to-date AGKA protocols, but our protocol achieves the strongest active security in AGKA protocols, so far.

1.2 Related Work

As a fundamental primitive of secure group communications, GKA has attracted considerable attention in cryptography. The best-known among these are perhaps the works of Ingemarsson et al. [16], Burmester and Desmedt [5], and Steiner et al. [20]. These proposals require two or more rounds to obtain a secret key and an additional round for each member to confirm the established secret key. Boneh and Silverberg [4] showed that a one-round GKA protocol can be constructed if multilinear maps [15] exist. However, the key confirmation step cannot be eliminated. Further, these GKA protocols only allow secure intra-group communications.

Wu et al. [21] constructed a one-round AGKA protocol allowing a sender not in the group to encrypt to the members while offering short ciphertexts and efficient encryption. Unlike previous GKA protocols, an interesting property of Wu et al.’s AGKA protocol is that it allows key confirmation without extra communication. That is, a member just needs to locally encrypt a message using the encryption key and then decrypt the corresponding ciphertext using her secret decryption key. If the messages are equal, then she obtains the keys correctly. Their protocol requires $\mathcal {O}(1)$-size ciphertext and $\mathcal {O}(1)$ encryption operations after the group encryption key is negotiated. One may note that a trivial solution of one-round AGKA is to let each member publish a public key and withhold the respective secret key. A sender can then separately encrypt to each member and can generate the final ciphertext by concatenating all the underlying individual ones. However, this solution leads to $\mathcal {O}(n)$-size ciphertext and requires $\mathcal {O}(n)$ encryption operations for a group of $n$ receivers. The challenge is to design one-round AGKA protocols with efficient encryption and short ciphertexts.

Subsequently, Wu et al. strengthened AGKA and presented contributory broadcast encryption [22] so that the sender could exclude some members from reading the transmissions. In [23], Wu et al. showed how to shorten the size of protocol transcripts in AGKA protocols.

To alleviate complicated certificate management of authenticated GKA in the PKI setting, identity-based authenticated GKA protocols (e.g., [8, 17]) have been suggested. These protocols require two or more rounds and cannot cope with sender changes. The recent IBAAGKA protocol [26, 27] is one-round and can handle sender changes efficiently. However, this protocol only achieves partial forward secrecy. Further, to guarantee the security of the protocol, an additional identity-based signature is used which makes the protocol less interesting. One may consider adding random secret value(s) [6] in the key agreement phase of conventional GKA protocols to achieve escrow freeness in identity-based AGKA protocols. However, it is unclear how to use this method without affecting the round efficiency of AGKA protocols.

Another notion close to IBAGKA is identity-based broadcast encryption [11] due to Delerablée. However, since the long-term key derived from a member’s identity is directly used for decryption, identity-based broadcast encryption cannot even achieve partial forward secrecy and is weaker than our protocol with escrow freeness, which implies perfect forward secrecy.

Escrow freeness is especially important in the IBC setting since the KGC is the Achilles’ heel and the most vulnerable spot for an attacker to break. Many works have considered solutions to address this problem. For example, forward secrecy in identity-based (anonymous) key agreement protocols [9], anonymous ciphertext indistinguishability against KGC attack in identity-based encryption [10, 25], and resilience against continual auxiliary leakage of the master secret key in (hierarchical) identity-based encryption [24].

1.3 Paper Outline

The rest of the paper is organized as follows. Section 2 defines the security for IBAAGKA protocols. A strongly unforgeable stateful IBBMS signature is proposed in Sect. 3. Section 4 proposes our IBAAGKA protocol. Section 5 compares our AGKA protocol with other two AGKA protocols. Finally, Sect. 6 gives a conclusion.

2 System Model

In this section, we formalize our IBAAGKA model without escrow.

2.1 Notations

Let $\mathbb {P}$ be a polynomial-size set of participants. At any point of time, any subset $\mathbb {U}=\{\mathcal {U}_1, \ldots , \mathcal {U}_n\}\subseteq \mathbb {P}$ may decide to establish a confidential channel. Let $\varPi _{\mathcal {U}_i}^\pi$ represent instance $\pi$ of participant $\mathcal {U}_i$. We will require the following notations:

• $\mathsf{pid}_{\mathcal {U}_i}^\pi$ is the partner ID of $\varPi _{\mathcal {U}_i}^\pi$, defined by a set containing the identities of the participants in the group with whom $\varPi _{\mathcal {U}_i}^\pi$ intends to establish a session key including $\mathcal {U}_i$ itself. The identities in pid $_{\mathcal {U}_i}^\pi$ are lexicographically ordered.

• $\mathsf{sid}_{\mathcal {U}_i}^\pi$ is the session ID of instance $\varPi _{\mathcal {U}_i}^\pi$. The session IDs are unique. All members taking part in a given execution of a protocol have the same session ID. The session ID of $\varPi _{\mathcal {U}_i}^\pi$ can be instantiated by concatenating $\mathsf{pid}_{\mathcal {U}_i}^\pi$, a time interval (e.g., date of the day) and a counter of the number of sessions executed by the participants with partner ID $\mathsf{pid}_{\mathcal {U}_i}^\pi$ in the time interval.

• $\mathsf{ms}_{\mathcal {U}_i}^\pi$ is the concatenation of all messages sent and received by $\varPi _{\mathcal {U}_i}^\pi$ during its execution, where the messages are ordered by round, and within each round lexicographically by the identities of the purported senders.

• $\mathsf{ek}_{\mathcal {U}_i}^\pi$ is the group encryption key held by $\varPi _{\mathcal {U}_i}^\pi$.

• $\mathsf{dk}_{\mathcal {U}_i}^\pi$ is the group decryption key held by $\varPi _{\mathcal {U}_i}^\pi$.

• $\mathsf{state}_{\mathcal {U}_i}^\pi$ represents the current (internal) state of instance $\varPi _{\mathcal {U}_i}^\pi$. $\varPi _{\mathcal {U}_i}^\pi$ is terminated, if it stops sending and receiving; and it is successfully terminated if $\varPi _{\mathcal {U}_i}^\pi$ is terminated and no incorrect behavior has been detected, i.e., it possesses ek $_{\mathcal {U}_i}^\pi (\ne null)$, dk $_{\mathcal {U}_i}^\pi (\ne null)$, $\mathsf{ms}_{\mathcal {U}_i}^\pi$, pid $_{\mathcal {U}_i}^\pi$ and sid $_{\mathcal {U}_i}^\pi$.

Definition 1

(Partnering ). Two instances $\varPi _{\mathcal {U}_i}^\pi$ and $\varPi _{\mathcal {U}_j}^{\pi '}$ (with $i\ne j$) are partnered if and only if (1) they are successfully terminated; (2) $\mathsf{pid}_{\mathcal {U}_i}^\pi$ = pid $_{\mathcal {U}_j}^{\pi '}$; and (3) sid $_{\mathcal {U}_i}^\pi$ = sid $_{\mathcal {U}_j}^{\pi '}$.

2.2 Security Model

Our security model for IBAAGKA protocols is defined by the following game, which is run between a challenger $\mathcal {C}$ and an adversary $\mathcal {A}$. The adversary has full control of the network communications. This game has the following stages:

Initialize: Taking as input a security parameter $\ell$, $\mathcal {C}$ generates the master-secret and initializes the system parameters $\varUpsilon$. $\varUpsilon$ is passed to $\mathcal {A}$.

Probing: At this stage, $\mathcal {A}$ is allowed to make the following types of queries:

• Send $(\varPi _{\mathcal {U}_i}^\pi ,\varPsi )$: It sends a message $\varPsi$ to instance $\varPi _{\mathcal {U}_i}^\pi$, and outputs the reply generated by this instance. In particular, if $\varPsi =(\mathsf{sid},\mathsf{pid})$, this query prompts $\mathcal {U}_i$ to initiate the protocol using session ID sid and partner ID pid. If $\varPsi$ is of incorrect format, the query returns $null$.

• Corrupt $(\mathcal {U}_i)$: It outputs the private key of participant $\mathcal {U}_i$ and can be used to model forward secrecy.

• Corrupt(KGC): It outputs the master-secret and can be used to model escrow freeness.

• Ek.Reveal $(\varPi _{\mathcal {U}_i}^\pi )$: It outputs the group encryption key ek $_{\mathcal {U}_i}^\pi$.

• Dk.Reveal $(\varPi _{\mathcal {U}_i}^\pi )$: It outputs the group decryption key dk $_{\mathcal {U}_i}^\pi$. It is used to model known-key security.

• Test $(\varPi _{\mathcal {U}_i}^\pi )$: At some point, $\mathcal {A}$ returns two messages $(m_0,m_1)$ and a fresh instance $\varPi _{\mathcal {U}_i}^\pi$ (see Definition 2). $\mathcal {C}$ randomly chooses a bit $b\in \{0,1\}$, encrypts $m_b$ under ek $_{\mathcal {U}_i}^\pi$ to produce a ciphertext $c$, and returns $c$ to $\mathcal {A}$. This query can be queried only once and is used to model secrecy.

Following [21, 26, 27], we use the confidentiality of the final broadcast channel to define the secrecy of IBAAGKA protocols. That is, secrecy is defined by the indistinguishability of a message encrypted under the negotiated group encryption key from a random string in the ciphertext space.

Guess: Finally, $\mathcal {A}$ returns a bit $b'$. If $b' = b$, $\mathcal {A}$ wins the game. $\mathcal {A}$’s advantage is defined to be $\epsilon =|2\Pr [b = b'] -1|$.

Definition 2

(Freshness ). An instance $\varPi _{\mathcal {U}_i}^\pi$ is fresh if none of the following happens:

• 1. $\varPi _{\mathcal {U}_i}^\pi$ has not successfully terminated.

• 2. $\mathcal {A}$ has queried Dk.Reveal $(\varPi _{\mathcal {U}_i}^\pi )$ or Dk.Reveal $(\varPi _{\mathcal {U}_j}^{\pi '})$, where $\varPi _{\mathcal {U}_j}^{\pi '}$ is any partnered instance of $\varPi _{\mathcal {U}_i}^\pi$.

• 3. Before $\varPi _{\mathcal {U}_i}^\pi$ successfully terminated, the query Corrupt(KGC) has been made or the query Corrupt(participant) has been made for some participants whose identities are in $\mathsf{pid}_{\mathcal {U}_i}^\pi$.

Definition 3

(Secrecy ). An IBAAGKA protocol is said to be semantically indistinguishable against chosen identity and plaintext attacks (Ind-ID-CPA) if $\epsilon$ is negligible for any probabilistic polynomial time (PPT) active adversary in the above model.

We stress that, in our IBAAGKA secrecy definition, escrow freeness is incorporated since the attacker is allowed to corrupt the PKG. Even if such an attacker cannot understand the secret messages exchanged among the group members. The escrow freeness naturally implies perfect forward secrecy. This strong security is important in practice as IBAAGKA protocols are assumed to be deployed in ad hoc network like scenarios. In these applications, end users are usually connected by open wireless communications and exposed to attackers. Furthermore, the centralized PKG is the single point of the system and may be compromised by attackers. Our key-escrow free secrecy guarantees that IBAAGKA protocols can be securely employed in such hostile environments.

Similarly to [21, 26, 27], in the above model, we only consider chosen-plaintext attacks (CPA) against IBAAGKA protocols. We note our definition is readily extended to resist chosen-ciphertext (CCA) attacks. Indeed, there are some generic approaches that convert a CPA secure encryption scheme into a CCA secure one, such as the Fujisaki-Okamoto conversion [13].

3 Building Block: Strongly Unforgeable Stateful IBBMS

Here we propose a strongly unforgeable stateful IBBMS scheme as a building block of our IBAAGKA protocol.

3.1 Definition

A stateful IBBMS allows multiple signers to sign $t$ messages under a piece of state information in an efficient way to generate a batch multi-signature. Furthermore, the batch multi-signature can be separated into $t$ individual multi-signatures. A stateful IBBMS scheme consists of the following five algorithms:

• BM.Setup, taking as input a security parameter $\ell$, outputs a master-secret and a list of system parameters. For brevity, we omit the inclusion of the system parameters as part of the inputs for the other algorithms.

• BM.Extract, taking as inputs an entity’s identity $ID_i$ and the master-secret, outputs the entity’s private key.

• Sign, taking as inputs $t$ messages, a piece of state information $info$, a signer’s identity $ID_i$ and private key, outputs a batch signature.

• Aggregate, taking as input a collection of $x$ batch signatures on the same $t$ messages from $x$ signers, under the same state information $info$, outputs a batch multi-signature.

• BM.Verify, taking as input a batch multi-signature on $t$ messages generated by $x$ signers, under the same state information $info$, outputs either “all valid” if the batch multi-signature is valid or an index set, which means that the multi-signatures on the messages with indices in that set are valid.

As the state information, one can use the identities of all the signers and concatenate a specification of each time interval together with a counter of the number of signatures issued by these signers in the time interval.

3.2 Security Model

This section defines the strong unforgeability of stateful IBBMS schemes. Roughly speaking, a stateful IBBMS scheme is strongly unforgeable if an adversary cannot generate a different multi-signature on a message $m$ under any state information and $x$ signers’ identities even if he can get the signature(s) on $m$ under the same state information and identities. The formal definition of strong unforgeability of stateful IBBMS schemes is defined using the following game between a challenger $\mathcal {C}$ and an adversary $\mathcal {A}$.

Initialize: $\mathcal {C}$ runs BM.Setup to generate a master-secret and the system parameter list $\varUpsilon$. $\varUpsilon$ is passed to $\mathcal {A}$ while master-secret is kept secret.

Probing: $\mathcal {A}$ can adaptively issue the following queries:

• BM.Extract: $\mathcal {A}$ can request the private key of an entity with identity $ID_i$. On receiving such a query, $\mathcal {C}$ outputs the private key of this entity.

• Sign: $\mathcal {A}$ can request a batch signature on messages $(m_1, \ldots , m_{t_i})$ under an identity $ID_i$ and a piece of state information. For simplicity, we assume the messages are lexicographically ordered. On input

  $$(ID_i,info_i, m_1, \ldots , m_{t_i})$$

  the challenger $\mathcal {C}$ outputs a valid batch signature on those messages. If $\mathcal {A}$ asks a batch signature query with a previously used state information but different messages as input, $\mathcal {C}$ returns $null$.

Note that, to generate the IBBMS on messages $(m_1, \ldots , m_{t_i})$ under identities $(ID_1, \ldots$, $ID_x)$ (lexicographically ordered) and a piece of state information, $\mathcal {C}$ just needs to simulate via repeated calls to the Sign queries and then generate an IBBMS by using the Aggregate algorithm.

Forgery: Finally, $\mathcal {A}$ outputs $x$ identities $(ID_1^*, \ldots , ID_x^*)$, a piece of state information $info^*$, a message $m^*$ and a multi-signature $\sigma ^*$. $\mathcal {A}$ wins the game if the following conditions are satisfied:

• 1. $\sigma ^*$ is a valid multi-signature on message $m^*$ under identities $(ID_1^*, \ldots , ID_x^*)$ and $info^*$.

• 2. None of the identities in $\{ID_1^*, \ldots , ID_x^*\}$ has been submitted during the BM.Extract queries.

• 3. For $ID_i^*\in \{ID_1^*, \ldots , ID_x^*\}$, the forged signature $\sigma ^*$ is not generated by using the batch signatures output by calling the Sign queries with

  $$(ID_i^*, info^*, m_1, \ldots , m_\mathcal {I}, \ldots , m_t)$$

  as input, where $m_\mathcal {I}=m^*$ and $\mathcal {I}$ defines the index of the message.

In the Forgery stage, $\mathcal {A}$ is only required to output a single multi-signature, but not a batch multi-signature. This is due to the property of batch multi-signatures. A batch multi-signature can be separated into $t$ individual multi-signatures. We only require that one of them is a forgery. As a result, we require that none of the identities in $\{ID_1^*, \ldots , ID_x^*\}$ has been submitted during the BM.Extract queries. This restriction is stronger than the restriction in the security models for normal multi-signature schemes which allow an adversary to query $x-1$ private keys corresponding to the identities in $\{ID_1^*, \ldots , ID_x^*\}$. However, this level of security suffices for our higher level applications in IBAAGKA. Indeed, we will be reducing the security of our IBAAGKA to that of our IBBMS.

Definition 4

A stateful IBBMS scheme is strongly existentially unforgeable under adaptively chosen-message attacks if and only if the success probability $\epsilon '$ of any PPT adversary in the above game is negligible.

3.3 Strongly Unforgeable Stateful IBBMS Scheme

Before delving into the details of our construction, we would like to remark that, although our final goal is not to propose an identity-based multi-signature scheme, we borrow some of its design principles to achieve our final goal of building IBAAGKA. Hence, we do not consider the generic approach of building identity-based signatures from the certification approach of standard signatures [14].

Our scheme is built over bilinear groups. Let $\mathbb {G}_1$ and $\mathbb {G}_2$ be two multiplicative groups of prime order $q$, and $g$ be a generator of $\mathbb {G}_1$. An efficient map $\hat{e}: \mathbb {G}_1\times \mathbb {G}_1 \rightarrow \mathbb {G}_2$ is called a bilinear map if it satisfies the following two properties.

• 1. Bilinearity: It holds that $\hat{e}(g^\alpha , g^\beta ) = \hat{e}(g, g)^{\alpha \beta }$ for all $\alpha ,\beta \in \mathbb {Z}_q^*$.

• 2. Non-degeneracy: There exists $u,v\in \mathbb {G}_1$ such that $\hat{e}(u, v)\ne 1$.

Now we are ready to describe our strongly unforgeable stateful IBBMS scheme.

• BM.Setup: On input a security parameter $\ell$, KGC chooses two cyclic multiplicative groups $\mathbb {G}_1$, $\mathbb {G}_2$ with prime order $q$, such that there exists a bilinear map $\hat{e}:\mathbb {G}_1\times \mathbb {G}_1\longrightarrow \mathbb {G}_2$, where $\mathbb {G}_1$ is generated by $g$; KGC chooses a random $\kappa \in \mathbb {Z}_q^*$ as the master-secret and sets $g_{pub} =g^\kappa$; KGC chooses cryptographic hash functions

  $$H_1,H_2,H_3:\{0, 1\}^*\longrightarrow \mathbb {G}_1, H_4:\{0, 1\}^*\longrightarrow \mathbb {Z}_q^*$$

  Finally, KGC publishes the system parameter list

  $$\varUpsilon =(q,\mathbb {G}_1,\mathbb {G}_2,\hat{e}, g, g_{pub},H_1\sim H_4)$$

• BM.Extract: This algorithm takes $\kappa$ and an entity’s identity $ID_i\in \{0, 1\}^*$ as inputs. It generates the private key for the entity as follows:

  • 1. Compute

    $$id_{i,0}= H_1(ID_i,0),id_{i,1}= H_1(ID_i,1)$$

  • 2. Output the private key

    $$(s_{i,0} =id_{i,0}^{\kappa },s_{i,1} =id_{i,1}^{\kappa })$$

• Sign: To sign $t$ messages $(m_1, \ldots , m_t)$ under a piece of state information $info$, a signer with identity $ID_i$ and private key $(s_{i,0},s_{i,1})$ performs the following steps:

  • 1. Choose random $\eta _i,\theta _i\in \mathbb {Z}_q^*$ and compute

    $$\begin{aligned} r_i=g^{\eta _i}, u_i=g^{\theta _i}, v=H_2(info), \varpi _i=H_4(info,ID_i,r_i,u_i) \end{aligned}$$
    $$\begin{aligned} f_{j}=H_3(info,m_j), z_{i,j}=s_{i,0}s_{i,1}^{\varpi _i}v^{\theta _i}f_j^{\eta _i}, ~\text {for}~ 1\le j \le t. \end{aligned}$$

  • 2. Output batch signature $\sigma _{i}=(r_i,u_i,z_{i,1}, \ldots , z_{i,t})$.

• Aggregate: Anyone can aggregate a collection of signatures

  $$\{\sigma _{i}=(r_{i},u_i,z_{i,1}, \ldots , z_{i,t})\}_{1\le i \le x}$$

  on the messages $\{m_j\}_{1\le j \le t}$ from $x$ signers, under same $info$, into a batch multi-signature. In particular, the signatures can be aggregated into

  $$(r_1, \ldots , r_x,u_1, \ldots , u_x,d_1, \ldots , d_t), ~\text {where} ~d_j=\prod _{i=1}^x z_{i,j}.$$

• BM.Verify: To check the validity of the above batch multi-signature

  $$(r_1, \ldots , r_x, u_1, \ldots , u_x,d_1, \ldots , d_t)$$

  the verifier computes

  $$w=\prod _{i=1}^x r_i,y=\prod _{i=1}^x u_i,v=H_2(info),$$
  $$f_{j}=H_3(info,m_j), \varGamma _j=\hat{e}(f_j,w) ~\text {for}~ 1\le j \le t,$$
  $$\varpi _i=H_4(info,ID_i,r_i,u_i) ~\text {for} ~1\le i\le x,$$
  $$\varOmega =\hat{e}(\prod _{i=1}^x H_1(ID_i,0)H_1(ID_i,1)^{\varpi _i},g_{pub})\hat{e}(v,y).$$

  For $1\le j \le t$, the verifier checks

  $$\hat{e}(d_j,g)\mathop {=}\limits ^{?}\varOmega \varGamma _j.$$

  If all the equations hold, the verifier outputs “all valid”; otherwise, it outputs an index set $\mathbb {I}$, which means that the multi-signatures with indices in that set are valid.

The security of our protocol is based on the following computational Diffie-Hellman (CDH) assumption.

CDH Assumption: In a finite cyclic group $\mathbb {G}$ with order $q$, the CDH assumption states that, given $g, g^\alpha , g^\beta \in \mathbb {G}$ for randomly chosen $\alpha ,\beta \in \mathbb {Z}_q$, there exists no efficient algorithm to compute $g^{\alpha \beta }$.

The following result relates the security of the IBBMS primitive with the difficulty of breaking the CDH assumption.

Theorem 1

Let $H_1, H_2, H_3$ and $H_4$ be random oracles. Suppose an adversary $\mathcal {A}$ makes at most $q_{H_i}$ queries to $H_i$, for $1\le i\le 3$, $q_E$ Extract queries, $q_\sigma$ Sign queries with maximal message size $N$, and wins the game in Sect. 3.2 with advantage $\epsilon '$ in time $\tau '$; and the forged IBBMS is by at most $x$ users. Then, there exists an algorithm to solve the CDH problem with advantage

$$(\frac{x+2}{q_E+q_{H_3}+x+1})^{x+2} \frac{q_{H_3}}{e^{x+2}}\epsilon '$$

in time

$$\tau '+\mathcal {O}(4q_{H_1}+q_{H_2}+q_{H_3}+5Nq_\sigma )\tau _{\mathbb {G}_1}$$

where $\tau _{\mathbb {G}_1}$ is the time to compute a scalar exponentiation in $\mathbb {G}_1$ and $e$ is Euler’s number.

The proof will be presented in the full version of this paper.

4 Identity-Based Authenticated Asymmetric Group Key Agreement Protocol

In this section, we propose our one-round IBAAGKA protocol.

• Setup: It is the same as BM.Setup, except that an additional cryptographic hash function $H_5:\mathbb {G}_2\longrightarrow \{0,1\}^\iota$ is chosen, where $\iota$ defines the bit-length of plaintexts. The system parameter list is

  $$\varUpsilon =(q,\mathbb {G}_1,\mathbb {G}_2,\hat{e}, g, g_{pub},H_1\sim H_5,\iota )$$

• Extract: It is the same as BM.Extract.

• Agreement: Assume the group scale is $n$ and the session ID is $\mathsf{sid}_\lambda$. A protocol participant $\mathcal {U}_i$, whose identity is $ID_i$ and private key is $(s_{i,0},s_{i,1})$, performs the following steps:

  • 1. Choose $\eta _i,\theta _i\in \mathbb {Z}_q^*$ and compute

    $$r_i=g^{\eta _i},u_i=g^{\theta _i}$$

  • 2. Compute

    $$v=H_2(\mathsf{sid}_\lambda ),\varpi _i=H_4(\mathsf{sid}_\lambda ,ID_i,r_i,u_i)$$

  • 3. For $1\le j \le n$, compute

    $$f_{j}=H_3(\mathsf{sid}_\lambda ,j)$$

  • 4. For $1\le j \le n$, compute

    $$z_{i,j}=s_{i,0}s_{i,1}^{\varpi _i}v^{\theta _i}f_j^{\eta _i}$$

  • 5. Publish

    $$\sigma _{i}=(r_i,u_i,\{z_{i,j}\}_{j\in \{1, \ldots , n\},j\ne i})$$

• EncKeyGen: To get the group encryption key, for $j\in \{1,2\},i\in \{1, \ldots , n\}$, an entity computes

  $$v=H_2(\mathsf{sid}_\lambda ),f_{j}=H_3(\mathsf{sid}_\lambda ,j), \varpi _i=H_4(\mathsf{sid}_\lambda ,ID_i,r_i,u_i).$$

  Define $\varDelta =1$, if Eqs. (1) and (2) hold, and $\varDelta =0$ in other cases.

  $$\begin{aligned} \begin{aligned} \hat{e}(z_{1,2},g) \mathop {=}\limits ^{?}\hat{e}(H_1(ID_1,0)H_1(ID_1,1)^{\varpi _1},g_{pub})\hat{e}(v,u_1)\hat{e}(f_2,r_1) \end{aligned} \end{aligned}$$

  (1)
  $$\begin{aligned} \begin{aligned} \hat{e}(\prod _{i=2}^n z_{i,1},g) \mathop {=}\limits ^{?} \hat{e}(\prod _{i=2}^n H_1(ID_i,0)H_1(ID_i,1)^{\varpi _i},g_{pub}) \hat{e}(v,\prod _{i=2}^n u_i) \hat{e}(f_1,\prod _{i=2}^n r_i) \end{aligned} \end{aligned}$$

  (2)

  The $\varDelta$ is used to check whether $r_i$ and $u_i$ are well formatted. If $\varDelta =1$, the entity outputs $(w,\varOmega )$ as the group encryption key, where

  $$w=\prod _{i=1}^n r_i, \varOmega =\hat{e}(\prod _{i=1}^nH_1(ID_i,0)H_1(ID_i,1)^{\varpi _i},g_{pub})\hat{e}(v,\prod _{i=1}^n u_i);$$

  otherwise it aborts. We note that a protocol participant does not need to test the value of $\varDelta$, since it will do a similar check in the following DecKeyGen stage.

• DecKeyGen: Each participant $\mathcal {U}_i$ computes

  $$w=\prod _{l=1}^n r_l,\varGamma _i=\hat{e}(f_i,w),d_i=\prod _{l=1}^n z_{l,i}$$

  and tests

  $$\begin{aligned} \hat{e}(d_i,g)\mathop {=}\limits ^{?} \varOmega \cdot \varGamma _i. \end{aligned}$$

  If the equation holds, $\mathcal {U}_i$ accepts $d_i$ as the group decryption key; otherwise, it aborts. The above test is also used by $\mathcal {U}_i$ to determine whether the encryption key is valid.

• Enc: To encrypt a plaintext $m$, select $\rho \in \mathbb {Z}_q^*$ and compute the ciphertext $c=(c_1,c_2,c_3)$ where

  $$\begin{aligned} c_1=g^\rho ,c_2=w^\rho ,c_3=m\oplus H_5(\varOmega ^\rho ). \end{aligned}$$

• Dec: To decrypt the ciphertext $c=(c_1,c_2,c_3)$, $\mathcal {U}_i$, whose group decryption key is $d_i$, computes

  $$m=c_3\oplus H_5(\hat{e}(d_i,c_1)\hat{e}(f_i^{-1},c_2)).$$

The following theorem characterizes the security of our IBAAGKA protocol. The security of our protocol relies on the $k$-Bilinear Diffie-Hellman Exponent (BDHE) assumption [3] which states that, in the bilinear group setting, given $g, h$, and $g_i=g^{\alpha ^i}$ in $\mathbb {G}_1$ for $i = 1,2, \ldots , k,k+2, \ldots , 2k$ as inputs, there exists no efficient algorithm to compute $\hat{e}(g,h)^{\alpha ^{k+1}}$.

Theorem 2

Let $H_2, H_3$ and $H_5$ be random oracles. Suppose that an adversary $\mathcal {A}$ makes at most $q_{H_i}$ queries to $H_i$, $i\in \{2,3,5\}$, $q_C$ Corrupt queries, $q_S$ Send queries, $q_{EK}$ Ek.Reveal queries and $q_{DK}$ Dk.Reveal queries, and wins the game with advantage $\epsilon$ in time $\tau$. Then there exists an algorithm to solve the k-BDHE problem with advantage at least

$$\frac{1-2\epsilon '}{q_{H_5}(q_{DK}+1)e} \epsilon $$

in time

$$T=\tau +\mathcal {O}(10q_{EK})\tau _{\hat{e}}+\mathcal {O}(q_{H_2}+q_{H_3}+2q_C+8q_S+3q_{EK})\tau _{\mathbb {G}_1}$$

where $\epsilon '$ is the advantage for $\mathcal {A}$ to forge a valid IBBMS in time $T$, $\tau _{\hat{e}}$ is the time to compute a bilinear map, $\tau _{\mathbb {G}_1}$ is the time to compute a scalar exponentiation in $\mathbb {G}_1$ and $e$ is Euler’s number.

The proof will be presented in the full version of this paper.

5 Comparison

In this section, we compare our AGKA protocol with the unauthenticated AGKA protocol in [21] and the IBAAGKA in [26, 27]. We only consider the costly operations and omit the operations that can be pre-computed.

Table 1 shows the computational overhead of three protocols in the last five stages, where $\tau _{\hat{e}}, \tau _{\mathbb {G}_1}, \tau _{H}, \tau _{\mathbb {G}_2},\tau _{sg}$ are the times to compute a bilinear map, a scalar exponentiation in $\mathbb {G}_1$, a MapToPoint hash, a scalar exponentiation in $\mathbb {G}_2$, and the signing algorithm of an identity-based signature (IBS), respectively. Let $\tau _{sv}$ denote the verification time of an IBS. The efficiency of an AGKA protocol is mainly determined by stages Enc and Dec, since Agreement, EncKeyGen and DecKeyGen only need to be run once. Hence, for simplicity, in EncKeyGen, we only consider the computational cost for a participant to generate the group encryption key; the computational cost for a sender to generate the group encryption key is omitted. From this table, one can find that our protocol has comparable efficiency in stages Agreement, EncKeyGen and DecKeyGen as protocols in [21, 26, 27]. For stages Enc and Dec, our protocol is as efficient as [26, 27], and it has similar efficiency as [21].

Table 1. Computational overhead ($\dag$: it can be done in EncKeyGen or DecKeyGen)

Let $P_1, P_2, P_{ID}, P_m$ denote the binary length of an element in $\mathbb {G}_1$, $\mathbb {G}_2$, an identity, and a message, respectively. Let $P_{sig}$ be the length of an identity-based signature. Table 2 compares our protocol with two other protocols regarding transmission cost. From this table, one may find that the transmission overhead of our protocol is slightly lower than the one in [21, 26, 27] for the Agreement stage, if we consider an identity of length 160 bits. Further, the length of a ciphertext in our protocol is the same as the one in [21, 26, 27], assuming that the plaintexts in the three protocols are of the same size.

Table 2. Transmission Overhead

6 Conclusion

We have extended the security model for IBAAGKA protocols, in which an attacker is allowed to learn the master secret of the KGC. A one-round IBAAGKA protocol has been proposed and proven secure in our extended model under the $k$-BDHE assumption. It offers secrecy and known-key security, and it does not suffer from the escrow problem. Therefore, not even the KGC can decrypt the ciphertexts sent to a group.