Anonymous Cluster-Based MANETs with Threshold Signature

Abstract

Security supports are a significant factor in the design of security system in ad hoc networks. It is particularly important to protect the identities of individual nodes to avoid personal privacy concerns. In this paper, we propose a security system for ID-based anonymous cluster-based MANETs to protect the privacy of nodes. Moreover, we propose a threshold signature scheme without pairing computations, which diminishes the computation load on each node. To the best of our knowledge, our proposed security system is the first in which the pseudonym is combined with cluster-based mobile ad hoc networks (MANETs) without a trusted entity. According to our protocol analysis, our proposal satisfies most properties for an anonymous security system and effectively copes with dynamic environments with greater efficiency by using secret sharing schemes. Therefore, it could be usefully applied to preserve privacy in dynamic MANETs without a trusted entity, such as military battlefields, emergency areas, mobile marketplaces, and vehicular ad hoc networks (VANETs).

1. Introduction

MANETs support communications in situations involving temporary self-organization and infrastructure-less situations, such as battlefields, disaster relief situations, and emergency rescue areas [1]. Recently, MANETs have been extended to intelligent transport systems, often called VANETs. However, MANETs are subject to various types of attacks because of the wireless and infrastructure-less environments in which they are used. Moreover, these network structures make it difficult to apply the certificate-based public key cryptosystem (CBC) to meet the requirements of the certificate authority (CA). As a powerful alternative to the CBC, the identity-based cryptosystem (IBC) proposed by Shamir [2] has been gaining momentum in recent years. It allows public keys to be derived from entities' known identity information, such as e-mail addresses, IP addresses, or codes, thus eliminating the need for public key distribution and certificates. In other words, a user's public key can be determined directly from his identifying information, rather than having to be extracted from a certificate issued by a CA.

However, a centralized public key generator (PKG) which generates a key pair for users in the IBC would obviously be easy to attack, and accessibility could not be guaranteed at all times for all participants in MANETs. To counter this, Boneh and Franklin [3] suggested spreading the PKG by means of distributed PKGs (D-PKGs), using threshold cryptography. Distribution of a signing key and CA functionality over multiple nodes using secret sharing and threshold cryptography is a possible solution to this problem. Most studies in cluster-based MANETs considering D-PKGs have been based on hierarchy topology structures, which classify the node into two types, namely, representative nodes, called clusterheads (CHs), and common nodes.

Furthermore, the threshold signature scheme in MANETs has attracted many researchers' attentions recently [4]. The threshold signature achieves the purpose for many individuals to cooperatively sign the same document. Some schemes with trusted party are proposed and applied to CBC-based networks [5], while these are unreasonable to MANETs where there are no infrastructure and control administration. Therefore, the threshold signature scheme is necessary for secure message transmission in MANETs. A recent research on cluster-based MANETs has sought to address the privacy problem [6] and threshold signature schemes [7], but research on anonymous threshold signature schemes in cluster-based MANETs has been insufficient.

This paper proposes a security system for ID-based anonymous cluster-based MANETs to protect the privacy of nodes. Moreover, we propose a threshold signature scheme without pairing computation, which diminishes the computation load on each node in comparison with existing schemes. The major contributions of this study are summarized as follows.

• (i)

Security of a cluster key distribution scheme and key agreement scheme. We propose a secure cluster key distribution scheme and a key agreement scheme with anonymity for cluster-based MAENTs. Cluster key distribution scheme ensures that the compromise of an arbitrary number of nodes outside the target cluster does not jeopardize the secrecy of noncompromised nodes. Key agreement scheme also ensures secure communication between nodes in intra- and interclusters.

(ii)

Consideration of threshold signature without pairing computation. Our threshold signature supports threshold signature. Comparing to existing threshold signatures, we diminish the computation load on signing nodes and a verification node; instead, CHs aid signature verification process. Thus, our threshold signature is suitable for the distributed PKGs architecture or the cluster-based network architecture.

(iii)

Protection of personal privacy. Our schemes support entity anonymity. Only the entities especially of the matched session can know the identity of others with whom they are in communication. For instance, CHs could be dealers, and common nodes could be purchasers when considering temporary established mobile markets. It is no needed to hide the CHs' identity because every purchaser should recognize CHs as dealers and their information; therefore, identities of CHs are not quite important. Besides, the information of purchasers is much attractive to adversaries because the information could be abusable commercially and criminally.

The rest of the paper is organized as follows. In Section 2, we present preliminaries, and the system model is presented in Section 3. In Section 4, we describe ID-based anonymous cluster-based MANETs, and the threshold signature is discussed in Section 5. Finally, we analyze the proposed scheme in Section 6 and conclude our findings in Section 7.

2. Preliminaries

In this section and we present notations, then define the cryptographic system and primitives used as building blocks in our security system.

2.1. Notations

Table 1 lists some important notations whose concrete meanings will be further explained where they appear for the first time.

Table 1

Notations.

${𝔾}_{\mathrm{1}},{𝔾}_{\mathrm{2}}$	Cyclic groups of order q
$\widehat{e}$	Pairing s.t. $\widehat{e}:{𝔾}_{\mathrm{1}}\times {𝔾}_{\mathrm{1}}\to {𝔾}_{\mathrm{2}}$
P	Generator of ${𝔾}_{\mathrm{1}}$
$\text{C}{\text{H}}_j/\text{I}{\text{D}}_A$	Network ID of clusterhead j/common node A
$\text{P}{\text{S}}_A$	Pseudonym of $\text{I}{\text{D}}_A$
$S_j/Q_j$	Private/public key pair of clusterhead $\text{C}{\text{H}}_j$
$S_A/Q_A$	Private/public key pair of common node $\text{I}{\text{D}}_A$
$S_{\text{P}{\text{S}}_A}/Q_{\text{P}{\text{S}}_A}$	Private/public key pair of pseudonym $\text{P}{\text{S}}_A$
U	Maximum update phase index
$K_m$	Cluster key at m-th update phase
$g_m(x)$	Polynomial for cluster key $K_m$ at m-th update phase
$f_m^{\text{C}{\text{H}}_j}(x)$	Polynomial of $\text{C}{\text{H}}_j$ at m-th update phase
$v_M^{\text{C}{\text{H}}_j}(x)$	Verifying polynomial of $\text{C}{\text{H}}_j$ for message M
$(t,n)$	Secret sharing parameters for $g_m(x)$
$(t_{\mathrm{1}},n_{\mathrm{1}})$	Secret sharing parameters for $f_m^{\text{C}{\text{H}}_j}(x)$
$H_{\mathrm{0}}$	Mapping $\{\mathrm{0,1}{\}}^{\mathrm{*}}\to {\mathbb{Z}}_p^{\mathrm{*}}$
$H_{\mathrm{1}}$	Mapping $\{\mathrm{0,1}{\}}^{\mathrm{*}}\to {𝔾}_{\mathrm{1}}$
$H_{\mathrm{2}}$	Mapping ${\mathbb{Z}}_p^{\mathrm{*}}\to \{\mathrm{0,1}{\}}^{\mathrm{*}}$
$H_{\mathrm{3}}$	Mapping ${𝔾}_{\mathrm{1}}\to {\mathbb{Z}}_p^{\mathrm{*}}$
$\text{HMA}{\text{C}}_K(M)$	Hash message authentication code of message M with key K

2.2. ID-Based Cryptography

Let $p,q$ be two large primes, and let $E/{𝔽}_p$ indicate an elliptic curve $y^{\mathrm{2}}=x^{\mathrm{3}}+ax+b$ over the finite field ${𝔽}_p$ . We denote by ${𝔾}_{\mathrm{1}}$ a q-order subgroup of the additive group of points of $E/{𝔽}_p$ and by ${𝔾}_{\mathrm{2}}$ a q-order subgroup of the multiplicative group of the finite field ${𝔽}_{p^{\mathrm{2}}}^{*}$ . The discrete logarithm problem (DLP) is required to be hard in both ${𝔾}_{\mathrm{1}}$ and ${𝔾}_{\mathrm{2}}$ . For us, a pairing is a map $\widehat{e}:{𝔾}_{\mathrm{1}}\times {𝔾}_{\mathrm{1}}\to {𝔾}_{\mathrm{2}}$ with the following properties.

• (i)

 Bilinear: for all $P,Q,R,S\in {𝔾}_{\mathrm{1}}$ ,

 

$\widehat{e}(P+Q,R+S)=\widehat{e}(P,R)\widehat{e}(P,S)\widehat{e}(Q,R)\widehat{e}(Q,S)$ .

 

Consequently, for all $a,b\in {\mathbb{Z}}_q^{*}$ , we have

 

$\widehat{e}(aP,bQ)=\widehat{e}(aP,Q{)}^b=\widehat{e}(P,bQ{)}^a=\widehat{e}(P,Q{)}^{ab}$ and so forth.

(ii)

 Nondegenerate: if P is a generator of ${𝔾}_{\mathrm{1}}$ , then $\widehat{e}(P,P)\in {𝔽}_{q^{\mathrm{2}}}^{*}$ is a generator of ${𝔾}_{\mathrm{2}}$ .

(iii)

 Computable: there is an efficient algorithm to compute $\widehat{e}(P,Q)$ for all $P,Q\in {𝔾}_{\mathrm{1}}$ .

Note that $\widehat{e}$ is also $symmetric$ , that is, $\widehat{e}(P,Q)=\widehat{e}(Q,P)$ , for all $P,Q\in {𝔾}_{\mathrm{1}}$ , which follows immediately from the bilinearity and the fact that ${𝔾}_{\mathrm{1}}$ is a cyclic group. Modified Weil [3] and Tate [8] pairings are examples of such bilinear maps for which the bilinear Diffie-Hellman problem (BDHP) is believed to be hard.

Definition 1 (bilinear Diffie-Hellman (BDH) problem).

The BDH problem for a bilinear pairing $\widehat{e}:{𝔾}_{\mathrm{1}}\times {𝔾}_{\mathrm{1}}\to {𝔾}_{\mathrm{2}}$ is defined as follows: given $P,xP,yP,zP\in {𝔾}_{\mathrm{1}}$ , where $x,y,z$ are random numbers from ${\mathbb{Z}}_p^{*}$ , compute $\widehat{e}(P,P{)}^{xyz}\in {𝔾}_{\mathrm{2}}$ .

Definition 2 (decisional Bilinear Diffie-Hellman (DBDH) problem).

The DBDH problem for a bilinear pairing $\widehat{e}:{𝔾}_{\mathrm{1}}\times {𝔾}_{\mathrm{1}}\to {𝔾}_{\mathrm{2}}$ is defined as follows: given $P,xP,yP,zP\in {𝔾}_{\mathrm{1}}$ , where $x,y,z$ are random numbers from ${\mathbb{Z}}_p^{*}$ and $W\in {𝔾}_{\mathrm{2}}$ that determine if $\widehat{e}(P,P{)}^{xyz}=W$ (if it holds), then the tuple $〈P,xP,yP,zP,W〉$ is called a BDH tuple.

2.3. Threshold Schemes Based on Secret Sharing

2.3.1. Shamir's $\mathbf{(}t\mathbf{,}n\mathbf{)}$ -SS

In Shamir's $(t,n)$ -SS [9], based on a Lagrange interpolating polynomial, there are n shareholders $𝒰=\{{𝒰}_{\mathrm{1}},\dots ,{𝒰}_n\}$ and a mutually trusted dealer D. The scheme consists of two algorithms.

• (1)

Share generation algorithm: dealer D does the following:

• (i)

  dealer D first picks a polynomial $f(x)$ of degree $(t-\mathrm{1})$ randomly: $f(x)=a_{\mathrm{0}}+a_{\mathrm{1}}x+\cdots +a_{t-\mathrm{1}}{x}^{t-\mathrm{1}}$ in which the secret $K=a_{\mathrm{0}}=f(\mathrm{0})$ and all coefficients $a_{\mathrm{0}},a_{\mathrm{1}},\dots ,a_{t-\mathrm{1}}$ are in a finite field ${𝔽}_p=GF(p)$ with p elements,

• (ii)

  D computes all shares: $K_i=f(s_i)$ (mod p) for $i=\mathrm{1},\dots ,n$ ,

• (iii)

  Then, D outputs a subset $\mathrm{\Omega }$ of size n, $(K_{\mathrm{1}},K_{\mathrm{2}},\dots ,K_n)$ , and distributes each share $K_i$ to corresponding shareholder $s_i$ privately.

(2)

Secret reconstruction algorithm: based on a Lagrange interpolation, any subset $A\subset \mathrm{\Omega }$ of size t can reconstruct the polynomial $f(x)$ as

$$\begin{array}{cc}& f\left(x\right)=\sum _{i\in A}{\lambda }_i\left(x\right)K_i\hspace{1em}\left(\mathrm{mod}\mathrm{\hspace{0.17em}\hspace{0.17em}}q\right),\end{array}$$

(1)

where $A=\{\mathrm{1},\dots ,t\}\subseteq \{\mathrm{1,2},\dots ,n\}$ , ${\lambda }_i(x)={\prod }_{j\in A\setminus i}((s_j-x)/(s_j-s_i))‍$ is called a Lagrange coefficient. The secret K can be reconstructed by computing $f(\mathrm{0})$ .

We note that the above scheme satisfies the basic security requirements of secret sharing schemes as follows: (1) with knowledge of a t or more than t shares, it can reconstruct the secret K easily; (2) with knowledge of fewer than $(t-\mathrm{1})$ shares, it cannot reconstruct the secret K. Shamir's scheme is information theoretically secure since the scheme satisfies these two requirements without making any computational assumption. For more information on this scheme, readers can refer to the original paper [9].

3. System Model

We describe the network architecture and the security requirements.

3.1. Network Architecture

We divide the networks into several clusters to enhance the efficiency and availability. The clustering is a method that enables nodes to be organized on the basis of their relative proximity to one another. We envision a cluster-based MANETs consisting of n CHs without any prior contact, trust, or authority relation. In each cluster, one distinguished node, the CH, is responsible for establishing and managing the cluster. The size of the network may change dynamically according to the efficiency and the security. Let us consider an ad hoc network with n CHs that are selected to enable secure and robust pseudonym generation. We assume that compromised CHs will eventually exhibit detectable misbehavior. Studies [10, 11] discussed ways to detect the misbehavior of nodes or intrusions in detail.

Our schemes work securely and properly on the assumption, which is similar to assumptions made in [12–14], that adversaries compromise no more than $(t-\mathrm{1})$ out of n CHs in a given time period. In practice, it is hard to compromise, in a given time period, t CHs, which are more secure and powerful than common nodes and are geographically distributed over a wide area. In terms of nodes' ability, we also assume that CHs have more computation and communication power than common nodes. More precisely, CHs have an additional powerful radio to establish wireless links among themselves and strong resistance against malicious attacks.

Figure 1(a) illustrates the basic network architecture of our security system for cluster setup and pseudonym generation. CHs have secret sharing $g_m(\text{C}{\text{H}}_j)$ generated by a PKG before implementation. CHs can generate polynomials $g_m(x)$ when at least t CHs collaborate in the secret reconstruction algorithm. The CHs that reconstruct $g_m(x)$ have the same cluster key, $K_m$ . This cluster key is periodically updated according to the update phase. Using the same cluster key, CHs generate their own polynomial $f_m^{\text{C}{\text{H}}_j}(x)$ , called the respective polynomial later. Finally, common nodes in each cluster register and receive a pair of pseudonym from their CHs. We only consider the privacy of common nodes.

Figure 1

Network Architectures.

Figure 1(b) illustrates the threshold signature generation process in a cluster. Nodes that are member of the same cluster and try to send the same message generate a threshold signature and send the message with a threshold signature to a verifier and the CH. Then, the CH checks the validity of messages and signatures and generates and sends additional points to a verifier. Finally, a verifier checks the validity of signatures.

3.2. Security Requirements

We define security requirements for our anonymous security system.

• (1)

Privacy: private information, such as the node's identity and location, should be protected against malicious adversaries. Formally, given two sets of legitimate identities, $\text{I}{\text{D}}_{\mathrm{0}}$ and $\text{I}{\text{D}}_{\mathrm{1}}$ , the adversary should not have any significant advantage in guessing $d=\mathrm{0}$ or $\mathrm{1}$ for the pseudonym $\text{P}{\text{S}}_d$ .

(2)

Traceability: compromised nodes are identified, and the corresponding identity and pseudonym should be revoked to protect networks against further threats.

(3)

Nonmanipulation: no nodes or CHs can computationally manipulate a pseudonym from an identity.

(4)

Verifiability: from the signature, the verifier can be convinced of the signer.

(5)

Undeniability: once a signer creates a valid signature, he cannot repudiate the signature creation.

(6)

Unforgeability: no nodes can forge a signature; it can only be replicated by the signer who creates it.

4. Anonymous Cluster-Based MANETs

4.1. System Setup

It is reasonable to assume that a trusted PKG could bootstrap the network, which itself is not a part of the resulting network. The basic operations consist of generating pairing parameters, private keys, and secret sharing.

• (a)

 Generation of the pairing parameters $(p,q,\widehat{e})$ : to bootstrap the network, the PKG does the following.

• (i)

  Generation of pairing parameters $(p,q,\widehat{e})$ . It selects an arbitrary generators $s\in {\mathbb{Z}}_q^{*}$ as its private key.

(b)

 Generation of secret sharing for cluster key: to generate secret sharing for cluster key, the PKG does the following.

• (i)

It submits identity information. A CH submits its identity information, $\text{C}{\text{H}}_j$ , where $(\mathrm{1}\le j\le n)$ , to PKG.

(ii)

It chooses cluster key. The PKG selects an arbitrary cluster keys $K_m\in {\mathbb{Z}}_q^{*}$ , where $(\mathrm{1}\le m\le U)$ .

(iii)

It determines polynomials of degree $(t-\mathrm{1})$ . The PKG determines random polynomials, $g_m(x)=K_m+{\sum }_{i=\mathrm{1}}^{t-\mathrm{1}}‍a_i{x}^i$ (mod q).

(iv)

It performs $(t,n)$ -SS of $K_m$ . The PKG computes $\text{c}{\text{h}}_j=H_{\mathrm{0}}(\text{C}{\text{H}}_j)$ and secret sharing of $g_m(x)$ : $g_m(\text{c}{\text{h}}_j)$ .

(v)

Parameters U, $g_m(\text{c}{\text{h}}_j)$ are preloaded to each $\text{C}{\text{H}}_j$ securely.

(c)

 Generation of CH's ID-based private keys: to hand out CH's private key, the PKG does the following.

• (i)

It submits identity information. A CH submits its identity information, $\text{C}{\text{H}}_j$ , to PKG.

(ii)

It computes key pairs. The PKG computes a public/private key pairs: $Q_j=H_{\mathrm{1}}(\text{C}{\text{H}}_j)$ and $S_j=s{H}_{\mathrm{1}}(\text{C}{\text{H}}_j)$ , $(\mathrm{1}\le j\le n)$ .

(iii)

Parameters $(p,q,G_{\mathrm{1}},G_{\mathrm{2}},\widehat{e},P,H_{\mathrm{0}},H_{\mathrm{1}},H_{\mathrm{2}},H_{\mathrm{3}})$ and key pairs $(Q_j,S_j)$ are preloaded to each $\text{C}{\text{H}}_j$ securely.

(d)

 Generation of common nodes' ID-based private keys: to hand out node's private key, the PKG does the following.

• (i)

It submits identity information. A common node submits its identity information, $\text{I}{\text{D}}_A$ , to PKG.

(ii)

It computes key pairs. The PKG computes a public/private key pairs: $Q_A=H_{\mathrm{1}}(\text{I}{\text{D}}_A)$ and $S_A=s{H}_{\mathrm{1}}(\text{I}{\text{D}}_A)$ , $(\mathrm{1}\le j\le n_{\mathrm{1}})$ .

(iii)

Parameters $(p,q,G_{\mathrm{1}},G_{\mathrm{2}},\widehat{e},P$ , $H_{\mathrm{0}},H_{\mathrm{1}},H_{\mathrm{2}},H_{\mathrm{3}})$ and key pairs $(Q_A,S_A)$ are preloaded to each $\text{I}{\text{D}}_A$ securely.

Due to the difficulty of solving the DLP in $G_{\mathrm{1}}$ , it is computationally infeasible to derive the network master secrets s from an arbitrary number of private keys. This means that no matter how many key pairs adversaries acquire from compromised nodes, they cannot deduce the private key of any noncompromised node. Colluding CHs (no more than $(t-\mathrm{1})$ out of n in a given time period) cannot compute a cluster key.

4.2. Cluster Setup

Cluster-based MANETs work without the help of PKG after completing the system setup. Instead of a PKG, CHs play this role using their secret sharing. In our security system, to provide security services to networks, each CH first generates respective polynomials, that cover within a cluster and a group secret key. Then, the CHs establish a secure channel with CHs or nodes to forward them. Secure channels are generated using their initial key pairs. Secure channels between CHs or between a CH and a node are established by the noninteractive key agreement scheme as follows:

$$\begin{array}{l}{D}_{AB}=\widehat{e}\left(Q_B,S_A\right)\\ \hspace{1em}\hspace{1em}=\widehat{e}{\left(H_{\mathrm{1}}\left(\text{I}{\text{D}}_B\right),H_{\mathrm{1}}\left(\text{I}{\text{D}}_A\right)\right)}^s=\widehat{e}\left(S_B,Q_A\right)=D_{BA},\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}{k}_{AB}=H_{\mathrm{2}}\left(D_{AB}\right).\end{array}$$

(2)

Here, A, B can be a node or a CH. Using this channel, CHs first authenticate nodes and other CHs and then forward respective polynomials and a group secret key. Respective polynomials are for cluster reconfiguration, and the group secret key is for establishing secure channels with pseudonyms. Generation of respective polynomials is carried out as follows.

• (1)

  Generate respective polynomials $f_m^{\text{C}{\text{H}}_j}(x)$ : to generate respective polynomials, CHs must reconstruct the polynomial $g_m(x)$ first. To reconstruct polynomials, $g_m(x)$ , and generate respective polynomials, $f_m^{\text{C}{\text{H}}_j}(x)$ , CHs do the following.

To avoid cryptanalysis and malfunction of CHs, frequent key updates are needed. Our key update schemes consist of two parts: one is an update of the cluster key, and the other is the respective polynomial. The cluster keys, $K_m$ , are refreshed periodically at a predefined time interval using secret sharing $g_m(\text{c}{\text{h}}_j)$ , where $(\mathrm{0}\le m\le U$ , $\mathrm{1}\le j\le n)$ . The cluster key update can enhance the security level of the network. Intact CHs reject secret sharing of compromised CHs and, as a result, are isolated from the networks. Furthermore, pseudonyms also could be updated consistently regardless of the cluster key update. Each CH can generate different pseudonyms with the same identity by changing a polynomial $f_m^{\text{C}{\text{H}}_j}(x)$ of its choice by replacing $b_i$ with $c_i,d_i,\dots$ .

4.3. Generation of Pseudonyms

Pseudonym generation is an essential process to provide privacy of each node. Figure 1(a) shows a scenario of pseudonym generation process. Initial pseudonym generation starts when the registered nodes on the PKG try to get a pseudonym from an adjacent CH. The CH generates pseudonyms for common nodes within a cluster using its respective polynomial. Pseudonyms and secret sharing are generated as follows.

• (1)

Generation of pseudonyms and key pair: to generate pseudonyms, CHs do the following.

• (a)

  Performing $(t_{\mathrm{1}},n_{\mathrm{1}})$ -SS of $K_m$ to generate pseudonyms. Each CH computes $\text{i}{\text{d}}_A=H_{\mathrm{0}}(\text{I}{\text{D}}_A)$ and secret sharing of $f_m^{\text{C}{\text{H}}_j}(x)$ : $\text{P}{\text{S}}_A=f_m^{\text{C}{\text{H}}_j}(\text{i}{\text{d}}_A)$ , where $(\mathrm{1}\le A\le n_{\mathrm{1}})$ .

• (b)

  Computing key pairs. Each CH computes a public/private key pairs: $Q_{\text{P}{\text{S}}_A}=\text{P}{\text{S}}_A{K}_{m}P$ and $S_{\text{P}{\text{S}}_A}=\text{P}{\text{S}}_A$ .

• (c)

  Recording pseudonyms. Each CH records the identities and the pseudonyms with the corresponding key pairs at the pseudonym lookup table (PLT).

• (d)

  Forwarding pseudonyms, key pairs, and group secret key to corresponding nodes. CHs forward pseudonyms to nodes, respectively, using a secure channel.

Other CHs cannot know pseudonyms from public keys of nodes even though they have knowledge of cluster key $K_m$ because of the hardness of DLP in $G_{\mathrm{1}}$ . Using the pseudonym key pair, common nodes establish a secure channel by the noninteractive key agreement scheme as follows:

$$\begin{array}{cc}& D_{AB}=\widehat{e}\left(Q_{\text{P}{\text{S}}_B},S_{\text{P}{\text{S}}_A}P\right)=\widehat{e}\left(Q_{\text{P}{\text{S}}_A},S_{\text{P}{\text{S}}_B}P\right)=\widehat{e}{\left(P,P\right)}^{\text{P}{\text{S}}_A\text{P}{\text{S}}_B{K}_m},\\ k_{AB}=H_{\mathrm{2}}\left(D_{AB}\right).\end{array}$$

(4)

For noninteractive key agreement between a CH and a node, each CH randomly chooses $r\in {\mathbb{Z}}_q^{*}$ and computes a temporary public key as $f_m^{\text{C}{\text{H}}_k}(r)K_{m}P$ then publishes it.

5. Threshold Signature in Anonymous Cluster-Based MANETs

We propose an anonymous threshold signature. The proposed scheme involves five roles: a clusterhead (CH), a set of members $ℳ=\{M_{\mathrm{1}},\dots ,M_{t_{\mathrm{1}}}\}$ in a cluster (where $M_{t_{\mathrm{1}}}$ is the identity of the ith $(\mathrm{1}\le i\le t_{\mathrm{1}})$ member), a set of signer $𝒮=\{S_{\mathrm{1}},\dots ,S_{t_{\mathrm{2}}}\}$ (where 𝒮 is a subset of ℳ and $S_{t_{\mathrm{2}}}$ is the identity of the jth $(\mathrm{1}\le j\le t_{\mathrm{2}})$ member), and a verifier V.

• (1)

Generate threshold signature: to generate a threshold signature regarding message M, a number of $t_{\mathrm{2}}$ nodes among the members of ℳ perform the following steps.

• (a)

  Requesting threshold generation. The initiator, one of signers, sends a threshold generation request to the CH with a list of signers as $\{T{S}_{\mathrm{1}},\dots ,T{S}_{t_{\mathrm{2}}}\}$ .

• (b)

  Sending tokens. The CH chooses an arbitrary tokens $T_A\in {\mathbb{Z}}_q^{*}$ , where $(\mathrm{1}\le A\le t_{\mathrm{2}})$ , and sends them to corresponding signers securely.

• (c)

  Generating signature. Then, each signer generates a signature: $\text{Si}{\text{g}}_{\text{P}{\text{S}}_A}=H_{\mathrm{0}}(M)·S_{\text{P}{\text{S}}_A}$ and computes with a corresponding token: $T·\text{Si}{\text{g}}_{\text{P}{\text{S}}_A}=T_A·\text{Si}{\text{g}}_{\text{P}{\text{S}}_A}$ .

• (d)

  Sending the signature and a pseudonym public key. Each node sends the message tuple to the verifier V and the $\text{C}{\text{H}}_j$ :

  $$\begin{array}{cc}& \left(M,Q_{\text{P}{\text{S}}_A},Q_{\text{P}{\text{S}}_V},T·\text{Si}{\text{g}}_{\text{P}{\text{S}}_A},\text{HMA}{\text{C}}_{\text{P}{\text{S}}_A}\left(M,Q_{\text{P}{\text{S}}_V},T·\text{Si}{\text{g}}_{\text{P}{\text{S}}_A}\right)\right),\end{array}$$

  (5)

(2)

Generate a verifying polynomial: to check the validity of signatures, the $\text{C}{\text{H}}_j$ performs the following steps:

• (a)

  Check the validity of a set of messages. The $\text{C}{\text{H}}_j$ searches corresponding pseudonyms with pseudonym public keys using the pseudonym lookup table (PLT) and then checks the validity of HMAC respectively.

• (b)

  Checking the validity of signatures. The $\text{C}{\text{H}}_j$ recovers signatures $\text{Si}{\text{g}}_{\text{P}{\text{S}}_A}$ from $T·\text{Si}{\text{g}}_{\text{P}{\text{S}}_A}$ using corresponding tokens and generates additional $(t_{\mathrm{1}}-t_{\mathrm{2}})$ points on $H_{\mathrm{0}}(M)·f_m^{\text{C}{\text{H}}_j}(x)$ . Then, it performs a secret reconstruction algorithm using $t_{\mathrm{2}}$ received signatures and $(t_{\mathrm{1}}-t_{\mathrm{2}})$ generated additional points. The reconstruction algorithm is as follows:

  $$\begin{array}{l}{H}_{\mathrm{0}}\left(M\right)·f_m^{\text{C}{\text{H}}_j}\left(x\right)=\sum _{i\in N}{\lambda }_i\left(x\right)Y_i\hspace{1em}\left(\mathrm{mod}\mathrm{\hspace{0.17em}\hspace{0.17em}}q\right),\\ \hspace{1em}\hspace{1em}{Y}_i=\{\begin{array}{ll}\text{Si}{\text{g}}_{\text{P}{\text{S}}_i},\hfill & \left(\mathrm{1}\le i\le t_{\mathrm{2}}\right),\hfill \\ H_{\mathrm{0}}\left(M\right)·\text{P}{\text{S}}_i,\hfill & \left(t_{\mathrm{2}}+\mathrm{1}\le i\le t_{\mathrm{1}}\right),\hfill \end{array}\end{array}$$

  (6)
  where $N=\{\mathrm{1},\dots ,t_{\mathrm{1}}\}$ , ${\lambda }_i(x)={\prod }_{j\in N\setminus i}‍((\text{i}{\text{d}}_i-x)/(\text{i}{\text{d}}_j-\text{i}{\text{d}}_i))$ is called a Lagrange coefficient. If the reconstructed polynomial has $H_{\mathrm{0}}(M)·K_m$ at $(x=\mathrm{0})$ , the $\text{C}{\text{H}}_j$ accepts signatures as valid.

• (c)

  Generating a verifying polynomial. If all messages and signatures are valid, the $\text{C}{\text{H}}_j$ generates an extra polynomial as follows:

(3)

Generate verification: to check the validity of a signature, the verifier does the following.

• (a)

  Performing secret reconstruction algorithm. The verifier performs a secret reconstruction algorithm using points $(P_{\mathrm{1}},\dots ,P_{t_{\mathrm{2}}})$ and the point $(\text{i}{\text{d}}_V,H_{\mathrm{0}}(M)·\text{P}{\text{S}}_V)$ . The verifying polynomial can be reconstructed as follows:

  $$\begin{array}{l}{v}_M^{\text{C}{\text{H}}_j}\left(x\right)=\sum _{i\in N_{\mathrm{1}}}{\lambda }_i\left(x\right)Z_i,\hspace{1em}\left(\mathrm{mod}\mathrm{\hspace{0.17em}\hspace{0.17em}}q\right),\\ \hspace{0.5em}{Z}_i=\{\begin{array}{ll}{P}_i,\hfill & \left(\mathrm{1}\le i\le t_{\mathrm{2}}\right),\hfill \\ H_{\mathrm{0}}\left(M\right)·\text{P}{\text{S}}_i,\hfill & \left(i=V\right),\hfill \end{array}\end{array}$$

  (8)
  where $N_{\mathrm{1}}=\{\mathrm{1},\dots ,t_{\mathrm{2}},V\}$ , ${\lambda }_i(x)={\prod }_{j\in N\setminus i}((\text{i}{\text{d}}_i-x)/(\text{i}{\text{d}}_j-\text{i}{\text{d}}_i))‍$ is called a Lagrange coefficient.

• (b)

  Checking the validity of HMAC. The verifier checks the validity of HMAC using received $t_{\mathrm{2}}$ points and generated $v_M^{\text{C}{\text{H}}_j}(\mathrm{0})$ . If HMAC is correct, the verifier identifies signatures as valid.

6. Analysis

In this section, we provide analysis of our system with respect to correctness, performance, and security.

6.1. Correctness

Note that

$$\begin{array}{cc}& f_m^{\text{C}{\text{H}}_j}\left(x\right)=K_m+\sum _{i=\mathrm{1}}^{t_{\mathrm{1}}-\mathrm{1}}‍b_i{x}^i=\sum _{i=\mathrm{1}}^{t_{\mathrm{1}}-\mathrm{1}}‍{\lambda }_i\left(x\right)\text{P}{\text{S}}_i,\\ \text{Si}{\text{g}}_{\text{P}{\text{S}}_i}=H_{\mathrm{0}}\left(M\right)·S_{\text{P}{\text{S}}_i}=H_{\mathrm{0}}\left(M\right)·\text{P}{\text{S}}_i,\end{array}$$

(9)

where $\text{P}{\text{S}}_i$ is the secret sharing of $K_m$ .

Therefore, a CH can verify the validity of each signature as follows:

$$\begin{array}{l}\sum _{i\in N}‍{\lambda }_i\left(x\right)Y_i=\sum _{i=\mathrm{1}}^{t_{\mathrm{2}}}‍{\lambda }_i\left(x\right)\text{Si}{\text{g}}_{\text{P}{\text{S}}_i}+\sum _{i=t_{\mathrm{2}}+\mathrm{1}}^{t_{\mathrm{1}}}‍{\lambda }_i\left(x\right)H_{\mathrm{0}}\left(M\right)\text{P}{\text{S}}_i\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}=H_{\mathrm{0}}\left(M\right)·\left\{\sum _{i\in N}‍{\lambda }_i\left(x\right)\text{P}{\text{S}}_i\right\}\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}=H_{\mathrm{0}}\left(M\right)·f_m^{\text{C}{\text{H}}_j}\left(x\right),\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}{H}_{\mathrm{0}}\left(M\right)·f_m^{\text{C}{\text{H}}_j}\left(\mathrm{0}\right)=H_{\mathrm{0}}\left(M\right)·K_m.\end{array}$$

(10)

The verifier also can check the validity of threshold signature as above, similarly, because $v_M^{\text{C}{\text{H}}_j}(x)$ passes a set of points $(P_{\mathrm{1}},P_{\mathrm{2}},\dots ,P_{t_{\mathrm{2}}})$ . The verifier can reconstruct the polynomial and find $v_M^{\text{C}{\text{H}}_j}(\mathrm{0})$ and, consequentially, check the validity of HMAC received from a CH.

6.2. Performance

This section presents our efficiency analysis. Table 2 compares our proposed schemes with other schemes. For simplicity, we omit private key distribution and secret sharing distribution process in comparison to computation load.

Table 2

Comparisons among other ID-based threshold signature schemes.

	[7]	[18]	[19]	Proposed scheme
Distributed PKG	∘	×	×	∘
Entity anonymity	×	×	×	∘
Cost of threshold signature
Cost of signature generation  (for one signer)	$\mathrm{4}{T}_P+\mathrm{3}t{T}_E+\mathrm{2}{T}_{M_{\mathrm{1}}}+\mathrm{3}t{T}_{M_{\mathrm{2}}}$	$T_P+t{T}_E+T_{M_{\mathrm{1}}}+t{T}_{M_{\mathrm{2}}}$	$\mathrm{2}{T}_P+\mathrm{2}t{T}_E+(\mathrm{2}t+\mathrm{2})T_{M_{\mathrm{1}}}+\mathrm{2}{T}_{M_{\mathrm{2}}}$	$\mathrm{2}{T}_{M_{\mathrm{2}}}$
Cost of signature validity check	$\mathrm{3}t{T}_P+t{T}_{M_{\mathrm{1}}}+t{T}_{M_{\mathrm{2}}}$   (for one signer)	$T_P+\mathrm{2}t{T}_E+\mathrm{2}t{T}_{M_{\mathrm{2}}}$   (for one signer)	Include in signature generation	$(t^{\mathrm{2}}+\mathrm{1})T_{M_{\mathrm{2}}}$   (for one CH)
Cost of signature verification   (for the verifier)	$\mathrm{6}{T}_P+\mathrm{2}{T}_M+\mathrm{2}{T}_S$	$\mathrm{2}{T}_P+T_E+T+H$	$\mathrm{2}{T}_P+\mathrm{2}{T}_{M_{\mathrm{1}}}$	$(t^{\mathrm{2}}-t)T_{M_{\mathrm{2}}}$

∘ denotes the scheme, and considers the property; × denotes the scheme and does not consider the property; $T_P$ denotes that of one pairing operation; $T_E$ denotes that of one exponentiation operation; $T_{M_1}$ denotes that of scalar multiplication in $G_1$ ; $T_{M_2}$ denotes that of one scalar multiplication in $G_2$ ; t denotes that signing nodes.

Most schemes use pairing algorithm to generate and verify the signature except the proposed scheme. The pairing algorithm and the exponentiation generally consume heavy computation loads rather than scalar multiplications. Cao et al. [15] showed a pairing that consumes about double computation load with those of an exponentiation and three times computation load with those of scalar multiplication in $G_{\mathrm{1}}$ . According to this experiment, our scheme is much lighter than previous threshold signature schemes. Moreover, our threshold scheme is comparable with existing threshold signatures in non-ID-based cryptosystem [16].

6.3. Security

6.3.1. Privacy

Our security system supports the anonymity of nodes using pseudonyms. In our proposed security system, every node does not reveal real identities after the pseudonym generation. An adversary cannot correctly match an identity with a pseudonym even though the identity and the pseudonym are released to them because of the hardness of DLP [17]. The pseudonym is in the form of $\text{P}{\text{S}}_A=f_m^{\text{C}{\text{H}}_j}(\text{i}{\text{d}}_A)$ in the mth update phase for node A in cluster j. To match a real identity with a pseudonym, adversaries should reconstruct a polynomial $f_m^{\text{C}{\text{H}}_j}(x)$ . However, no malicious nodes at most number of $(t-\mathrm{1})$ can reconstruct respective polynomials, although they have known about a cluster key $K_m$ because $(t_{\mathrm{1}},n_{\mathrm{1}})$ -SS is information theoretically secure against at most $(t_{\mathrm{1}}-\mathrm{1})$ adversaries. Thus, as long as the CH does not reveal the respective polynomials, anonymity of each node is guaranteed.

6.3.2. Traceability

Each CH records the relation of the identity and the pseudonym of common nodes in its cluster at the PLT. Pseudonyms of compromised and revoked nodes are rejected from the PLT, and these nodes cannot be updated any more. Therefore, our system enables the tracing of violators when unlawful actions are notified to the CH, and they are eventually isolated from the network.

6.3.3. Nonmanipulation

Our proposed security system ensures nonmanipulation in case of at most ( $t-\mathrm{1}$ or $t_{\mathrm{1}}-\mathrm{1}$ ) compromised nodes. Only the CH who has a respective polynomial can generate valid pseudonyms in a cluster, and no other nodes and CHs can do it. Secret sharing, $g_m(x)$ , is generated by $(t,n)$ -SS; therefore, no more than t CHs who are colluding can reconstruct $g_m(x)$ and learn $K_m$ ; and, to conclude, generate valid respective polynomials $f_m^{\text{C}{\text{H}}_k}(x)$ . Moreover, the respective polynomials generated by $(t_{\mathrm{1}},n_{\mathrm{1}})$ -SS are used to generate pseudonyms. In conclusion, adversaries who know more than t secret sharing of $g_m(x)$ or more than $t_{\mathrm{1}}$ secret sharing of $f_m^{\text{C}{\text{H}}_k}(x)$ can carry out manipulation; however, it is impractical. Thus, as long as (t or $t_{\mathrm{1}}$ ) or more than (t or $t_{\mathrm{1}}$ ) nodes and CHs are not colluding, non-manipulation is guaranteed.

6.3.4. Verifiability, Undeniability, and Unforgeability

The CH works as a subverifier in our threshold signature scheme by generating a verifying polynomial. From message tuples from signers, the CH can check the validity of signers. First, only valid and registered nodes could generate correct HMAC with its pseudonym. Second, the CH could verify signatures by reconstructing a polynomial $H_{\mathrm{0}}(M)·f_m^{\text{C}{\text{H}}_j}(x)$ . This polynomial returns a correct value $H_{\mathrm{0}}(M)·f_m^{\text{C}{\text{H}}_j}(\mathrm{0})=H_{\mathrm{0}}(M)·K_m$ when signatures are generated by signers who have a valid and registered pseudonym key pair. Finally, the reconstructed verifying polynomials generated by the CH and by the verifier return a same value, $v_M^{\text{C}{\text{H}}_j}(\mathrm{0})$ , when the CH satisfies two former conditions and has a valid pseudonym key pair of the verifier. Thus, verifiability is guaranteed if these conditions are acceptable. Undeniability and unforgeability are similarly guaranteed. The message containing the signature is in the form of $\text{HMA}{\text{C}}_{\text{P}{\text{S}}_A}$ . Unless the pseudonym is released, only the node A can generate valid HMAC; thus, it cannot deny the signature and others cannot forge it. Thus, undeniability and unforgeability are guaranteed.

6.3.5. Forward/Backward Secrecy

Our security system supports the forward/backward secrecy using key update scheme in case of at most ( $t-\mathrm{1}$ or $t_{\mathrm{1}}-\mathrm{1}$ ) compromised nodes. The key update scheme regularly updates pseudonyms, and, consequently, pseudonym public/private key pairs of nodes also are updated along to the updated pseudonym. And there is no relation in past key pairs and update key pairs because CHs periodically change a polynomial $f_m^{\text{C}{\text{H}}_j}(x)$ or a cluster key $K_m$ . Therefore, although the updated private/public key pairs are exposed to adversaries, these do not affect past and future session keys.

7. Conclusions

Concerns for personal privacy and security in wireless environments are increasing rapidly as mobile devices are becoming more popular. Cluster-based MANETs are being seriously considered to pioneer new markets; however, there are urgent unresolved security problems. Fundamental aspects of security, such as authentication and signature, are challenging for secure security systems for cluster-based MANETs. In addition, the protection of personal privacy has become increasingly important as the wireless networks have become personal and popular; therefore, secure security system designs with anonymity are required for cluster-based MANETs.

In this paper, we presented a secure security system with anonymity for cluster-based MANETs and a threshold signature under practical assumptions. To the best of our knowledge, our proposed security system is the first in which the pseudonym is combined with cluster-based MANETs without a trusted entity. According to our protocol analysis, our proposed system satisfies most properties for an anonymous security system and successfully copes with dynamic environments with greater efficiency by using secret sharing schemes. We believe that the proposed system improves upon the security of previously proposed security systems, and that it is suitable for a wider variety of applications. It could be usefully applied to preserve privacy in dynamic MANETs without a trusted entity, such as military battlefields, emergency areas, mobile marketplaces, and privacy-preserving VANETs.