Two Identity-Based Aggregate Signature Schemes from Pairings

Abstract

An aggregate signature is a short digital signature which is the output of aggregation process. The signature aggregation is done on k signatures of k distinct messages from k distinct users. As the produced signature size is shorter, so it will be efficient to use the schemes in low-bandwidth communication environment. In this paper, we proposed two identity-based aggregate signature schemes from bilinear pairing operations. The proposed schemes are secure against existential forgery under adaptively chosen message and identity attack in the random oracle model based on the assumption of intractability of the computational Diffie–Hellman problem (CDHP). The efficiency analysis of the proposed identity-based aggregate signature schemes with other established identity-based aggregate signature schemes is also done in this paper.

1 Introduction

In 2003, the first aggregate signature (BGLS), proposed by Boneh et al. [1] allows k members of a given group of potential signers to sign k different messages and all these signatures can be aggregated into a single signature. Actually, the aggregate signature [1] is based on the BLS [2] short signature.

As the size of aggregate signature is same as the individual signature, so we get a compact single signature of all individual signatures. This single signature can provide a proof to the verifier that the n players have indeed signed the original messages. Thus, aggregate signature provides non-repudiation security service on different messages signed by different users at the same time. Actually, there have been many practical application of aggregate signature scheme. As we are bounded by page limitation, only one example has been discussed. In public key infrastructure (PKI) of depth n, each user has been given a chain of certificate of length n. So, the chain contains n signatures by n certificate authorities (CAs) on n distinct certificate. If we use aggregate signature scheme, it is possible to obtain a compressed aggregated certificate [3]. Specifically, the main motivation is that X.509 certificates can be shortened into a single signature by compressing n signatures. It is also useful for compression where the signatures on many different messages are generated by many different users [4].

It is well known that that PKI-based cryptosystem has the biggest disadvantage related to certificate management activities. To avoid this problem, Shamir [5] introduced the concept of identity-based cryptosystem (IBC) in 1984. In IBC, the main advantage is that there is no need of public key distribution in the form of certificates as user can use his unique identity information such as name, email address by providing his own public key.

Due to various interesting practical applications and various advantages of IBC, discussed above, it is always a hot research area to achieve an efficient Id-based aggregate signature schemes. After the pioneering work [1, 2], many identity-based aggregate signature schemes have been proposed. In 2004, Cheon [6] presented first identity-based aggregate signature (IBAS). This scheme compresses the signatures into half, while the BGLS compresses multiple signatures into one. After that work, in 2006, Gentry and Ramzan proposed an efficient ID-based aggregate signature which is much faster than BGLS scheme as less number of operations are involved. In 2008, Wang [7] presented a new ID-based aggregate scheme which provides partial aggregation. It is also more efficient than BGLS scheme. At the same time, Wen [8] proposed a new aggregate signature with constant pairing operation (AS-CPO) scheme, which requires only two pairings in verification. This scheme is more efficient than BGLS as BGLS requires O(n) pairing computation where n is the number of signers. However, many ID-based aggregate signature schemes [7, 9, 10] have been constructed from basic ID-based signature scheme.

The rest of the paper is organized as follows. In the next section, mathematical background of the proposed schemes has been explained. After that, the two proposed schemes have been presented in the next section. In Sect. 4, the efficiency analysis of the proposed ID-based aggregate signature schemes with other established ID-based aggregate signature schemes has been done.

2 Mathematical Background

Bilinear Pairing: Let $G_{1}$ be an additive cyclic group generated by $P$ whose order is a prime $q$ and $G_{2}$ be a multiplicative cyclic group of the same order $q$. A bilinear pairing is a map $e:G_{1} \times G_{1} \to G_{2}$ with the following properties:

• (a) Bilinearity: $e\left( {aP, bQ} \right) = e(P;Q)^{ab}$ for all $P,Q \in G_{1}$ and all $b \in Z_{q}^{*}$.

• (b) Non-degenerate: There exists $P,Q \in G_{1}$ such that $e\left( {P,Q} \right) \ne 1$.

• (c) Computable: There is an efficient algorithm to compute $\left( {P,Q} \right)$, for all $P,Q \in G_{1}$.

Additionally, the security of these proposed schemes depends on the hardness of the following Diffiee–Hellman problem.

Computational Diffie–Hellman Problem (CDHP): For $b \in_{R} Z_{q}^{*}$, given $P,aP,bP$, to compute $abP$ is known as computational Diffie–Hellman problem which is a hard problem.

3 Two Proposed ID-Based Aggregate Signature Schemes

An aggregate signature scheme consists of six algorithms. They are Setup, Extract, Sign, Verify, AggSign, and AggVerify. The first four algorithms are for an ordinary identity-based signature scheme, and last two algorithms are for signature aggregation and aggregate signature verification. It works as follows. The first proposed aggregate signature scheme is presented in Sect. 3.1, and other one is presented in Sect. 3.2.

3.1 A Proposed ID-Based Aggregate Signature Schemes (First One)

SETUP: Given a security parameter $k,$ the private key generator (PKG) runs the setup algorithm and outputs two groups $G_{1}$ of prime order $q$ and $G_{2}$ of same order. The bilinear pairing is given as $e:G_{1} \times G_{2} \to G2.$ PKG establishes the system parameters $q,G_{1} ,G_{2} ,P,Q,P_{\text{pub}} ,P_{{{\text{pub}}^{2} }} ,e,H_{1} ,H_{2}$ where

• 1. $P$ is the generator of group $G_{1}$.

• 2. PKG picks master key $s \in Z_{p}^{ *}$ and computes $P_{\text{pub}} = sP,P_{{{\text{pub}}^{2} }} = s^{2} P$.

• 3. PKG also chooses two cryptographic hash functions, $H_{1} :\left\{ {0,1} \right\}^{*} \to G_{1}$ and $H_{2} :\left\{ {0,1} \right\}^{*} \to Z_{q}^{*}.$

EXTRACT: Let $P_{1} ,P_{2} , \ldots , P_{n}$ denote all the users to join the signing process. The identity of $P_{i}$ is denoted as $ID_{i}$. For user’s identity $ID_{i}$, its public key $Q_{{ID_{i} }} = H_{2} \left( {ID_{i} } \right)$ and private key $S_{{ID_{i} }} = sQ_{{ID_{i} }}$. The user makes $Q_{{ID_{i} }}$ public and keeps $S_{{ID_{i} }}$ secret.

SIGN: For a message $m_{i}$, user with identity $ID_{i}$ follows the steps below:

• 1. Choose a random number $r_{i} \in Z_{q}^{*}$, and broadcasts $U_{i} = r_{i} P.$

• 2. Calculate the value $h_{i} = H_{2} \left( {m_{i} ,ID_{i} ,U_{i} } \right)$

• 3. Calculate the value $V_{i} = r_{i} P + h_{i} S_{{ID_{i} }}$

• 4. The signature $\sigma_{i}$ is then the pair $\left( {U_{i} ,V_{i} } \right)$.

VERIFY:

• 1. The designated player (DP) computes $U = \sum\nolimits_{i = 1}^{n} {U_{i} .}$

• 2. Compute $h_{i} = H_{2} \left( {m_{i} ,ID_{i} ,U_{i} } \right)$

• 3. Accept if $e \left( {P_{\text{pub}} , V_{i} } \right) = e\left( {U_{i} ,P_{\text{pub}} } \right)e\left( {P_{{{\text{pub}}^{2} }} ,h_{i} Q_{{ID_{i} }} } \right)$

AGGSIGN: DP computes $V = \sum\nolimits_{i = 1}^{n} {V_{i} }$. The aggregate signature on $n$ different messages $m_{1} ,m_{2} , \ldots ,m_{n}$ given by $n$ users $P_{1} ,P_{2} , \ldots ,P_{n}$ is $\sigma = \left( {U,V} \right).$

AGGVERIFY: Given aggregate signature $\sigma = \left( {U,V} \right)$ by aggregating party and the list of $\left\langle {ID,message} \right\rangle$ pairs $\left\{ {ID_{i} ,m_{i} } \right\}$, the verifier verifies the aggregate signature compute

• 1.
  $$ h_{i} = H_{2} \left( {ID_{i} , m_{i} , U_{i} } \right). $$
• 2.
  $$ Q_{{ID_{i} }} = H_{1} \left( {ID_{i} } \right) $$

• 3. Accept the signature $\sigma = \left( {U,V} \right)$ if and only if

  $$ e\left( {P_{\text{pub}} ,V} \right) = e\left( {P_{\text{pub}} ,U} \right) \cdot e\left( {P_{{{\text{pub}}^{ 2} }} ,\sum\nolimits_{i = 1}^{n} {h_{i} Q_{{ID_{i} }} } } \right) $$

CORRECTNESS:

$$ \begin{aligned} e\left( {P_{\text{pub}} ,V} \right) & = e\left( {P_{\text{pub}} ,\sum\limits_{i = 1}^{n} {V_{i} } } \right) \\ & = \prod\limits_{i = 1}^{n} {e\left( {P_{\text{pub}} , V_{i} } \right)} = \prod\limits_{i = 1}^{n} {e\left( {P_{\text{pub}} ,r_{i} P + h_{i} S_{{ID_{i} }} } \right)} \\ & = e\left( {P_{\text{pub}} ,\sum\limits_{i = 1}^{n} {\left( {r_{i} P + h_{i} S_{{ID_{i} }} } \right)} } \right) = e\left( {P_{\text{pub}} ,\sum\limits_{i = 1}^{n} {\left( {r_{i} P + \sum\limits_{i = 1}^{n} {h_{i} S_{{ID_{i} }} } } \right)} } \right) \\ & = e\left( {P_{\text{pub}} ,U + \sum\limits_{i = 1}^{n} {h_{i} S_{{ID_{i} }} } } \right) = e\left( {P_{\text{pub}} , U} \right)e\left( {P_{\text{pub}} , \sum\limits_{i = 1}^{n} {h_{i} S_{{ID_{i} }} } } \right) \\ & = e\left( {P_{\text{pub}} ,U} \right)e\left( {s.P_{\text{pub}} , \sum\limits_{i = 1}^{n} {h_{i} Q_{{ID_{i} }} } } \right) = e\left( {P_{\text{pub}} ,U} \right)e\left( {P_{{{\text{pub}}^{ 2} }} ,\sum\limits_{i = 1}^{n} {h_{i} Q_{{ID^{i} }} } } \right) \\ \end{aligned} $$

3.2 Another Proposed Improved Identity-Based Aggregate Signature Scheme (Second One)

SETUP: Given a security parameter $k$, the private key generator (PKG) runs the setup algorithm and outputs two group $G_{1}$ of prime order $q\;{\text{and}}\;G_{2}$ of same order. The bilinear pairing is given ${\text{as}}\;e:G_{1} \times G_{1} \to G_{2} .$ PKG establishes the system parameters $q,G_{1} ,G_{2} ,P,Q,P_{\text{pub}} ,P_{{{\text{pub}}^{ 2} }} ,e,H_{1} ,H_{2}$ where

• 1. $P\;{\text{and}}\;Q$ are the random generators of group $G_{1} .$

• 2. PKG picks master key $s \in Z_{q}^{*}$ and computes $P_{\text{pub}} = sP,P_{{{\text{pub}}^{ 2} }} = s^{2} P.$

• 3. PKG also chooses two cryptographic hash functions, $H_{1} :\left\{ {0, 1} \right\}^{*} \to G_{1} \;{\text{and}}\;H_{2} :\left\{ {0, 1} \right\}^{*} \to Z_{q}^{*}.$

EXTRACT: Let $P_{1} ,P_{2} , \ldots ,P_{n}$ denote all the users to join the signing. The identity of $P_{i}$ is denoted as $ID_{i}$. For user’s identity $ID_{i}$, its public key $Q_{{ID_{i} }} = H_{2} \left( {ID_{i} } \right)$ and private key $s_{{ID_{i} }} = sQ_{{ID_{i} }}$. The user makes $Q_{{ID_{i} }}$ public and keeps $S_{{ID_{i} }}$ secret.

SIGN: For a message $m_{i}$, user with identity $ID_{i}$ follows the steps below:

• 1. Choose a random number $r_{i} \in Z_{q}^{*}$ and broadcasts $U_{i} = r_{i} P_{\text{pub}}$

• 2. Calculate the ${\text{value}}\;h_{i} = H_{2} \left( {m_{i} ,ID_{i} ,U_{i} } \right)$

• 3. Calculate the value $V_{i} = r_{i} Q + h_{i} S_{{ID_{i} }}$

• 4. The signature $\sigma_{i}$ is then the pair $\left( {U_{i} ,V_{i} } \right)$

VERIFY:

• 1. The designated player computes $U = \sum\nolimits_{i = 1}^{n}$

• 2. Compute $h_{i} = H_{2} \left( {m_{i} ,ID_{i} ,U_{i} } \right)$

• 3. Accept if $e\left( {P_{\text{pub}} ,V_{i} } \right) = e\left( {U_{i} ,Q} \right)e\left( {P_{{{\text{pub}}^{ 2} }} ,h_{i} Q_{{ID_{i} }} } \right)$

AGGSIGN: DP computes $V = \sum\nolimits_{i = 1}^{n} {V_{i} }$. The aggregate signature on $n$ different messages $m_{1} ,m_{2} , \ldots ,m_{n}$ given by $n$ users $P_{1} ,P_{2} , \ldots ,P_{n}$ is $\sigma = \left( {U,V} \right)$

AGGVERIFY: Given aggregate signature $\sigma = \left( {U,V} \right)$ by aggregating party and the list of $\left\langle {ID,message} \right\rangle$ pairs $\left\{ {ID_{i} ,m_{i} } \right\}$, the verifier verifies the signature by computing the following:

• 1. $h_{i} = H_{2} \left( {ID_{i} ,m_{i} ,U} \right)$

• 2. Accept the signature $\sigma = \left( {U,V} \right)$ if and only if

  $$ e\left( {P_{\text{pub}} ,V} \right) = e\left( {Q,U} \right).e\left( {P_{{{\text{pub}}^{ 2} }} ,\sum\nolimits_{i = 1}^{n} {h_{i} Q_{{ID_{i} }} } } \right) $$

• CORRECTNESS:

  $$ \begin{aligned} e\left( {P_{\text{pub}} ,V} \right) & = e\left( {P_{\text{pub}} ,\sum\nolimits_{i = 1}^{n} {V_{i} } } \right) \\ & = \prod\limits_{i = 1}^{n} {e(P_{\text{pub}} ,V_{i} )} \\ & = \prod\limits_{i = 1}^{n} {e(P_{\text{pub}} ,r_{i} Q + h_{i} S_{{ID_{i} }} )} \\ & = \prod\limits_{i = 1}^{n} {e(r_{i} P_{\text{pub}} ,Q)e\left( {sP_{\text{pub}} ,h_{i} Q_{{ID_{i} }} } \right)} \\ & = \prod\limits_{i = 1}^{n} {e(U_{i} ,Q)e(P_{{{\text{pub}}^{ 2} }} ,h_{i} Q_{{ID_{i} }} }) \\ & = e\left( {Q,\sum\limits_{i = 1}^{n} {U_{i} } } \right)e\left( {P_{{{\text{pub}}^{ 2} ,}} \sum\limits_{i = 1}^{n} {h_{i} Q_{{ID_{i} }} } } \right) \\ & = e\left( {Q,U} \right)e\left( {P_{{{\text{pub}}^{ 2} }} ,\sum\limits_{i = 1}^{n} {h_{i} Q_{{ID_{i} }} } } \right) \\ \end{aligned} $$

4 Efficiency Comparison

In this section, we will compare our schemes with the schemes in Refs. [7, 9, 10] as we have constructed these two schemes from the idea achieved from those papers. In general, the number of pairing computations of identity-based aggregate signature schemes (IBASs) is proportional to that of signers. But, our proposed IBAS schemes require constant number of pairing computations in aggregated signature verification process and are independent of the number of signers. An efficiency comparison of our schemes with the existing established schemes is given in Table 1. Here, $\Delta_{PO}$, $\Delta_{PA}$, $\Delta_{\text{Hash}}$, and $\Delta_{SM}$ denote the number of pairing operations, point addition in $G_{1}$ group, hash function, and scalar multiplications in $G_{1}$ group, respectively.

Table 1 Computational complexity of IBAS schemes in the number n of signers

5 Conclusion

In this paper, we propose two ID-based aggregate signature schemes with constant pairings needed in signature verification process. We observe that the first scheme is as same efficient as the scheme [10] which assumed to be the most efficient IBAS scheme until now. The security of the scheme is purely based on difficulty of solving computational Diffie–Hellman problem in the random oracle model. Due to page limitation, the security proof is not given in the paper. Just like all other pairing-based cryptosystems, it is not only simple and efficient but also has a shorter signature size.