Secure Private Key Revocation Scheme in Anonymous Cluster -Based MANETs
Secure Private Key Revocation Scheme in Anonymous Cluster -Based MANETs
Journal of Korea Multimedia Society. 2015. Apr, 18(4): 499-505
Copyright © 2015, Korea Multimedia Society
  • Received : November 27, 2014
  • Accepted : March 13, 2015
  • Published : April 30, 0015
Export by style
Cited by
About the Authors
YoHan Park
Department of Electronics Enginerring, Kyungpook National University
YoungHo Park
School of Electronics Engineering, Kyungpook National University

Security supports are a significant factor in the design of mobile ad hoc networks. In the dynamic topology where the node changes frequently, private key generation and revocation for newly joining and leaving nodes must be considered. In addition, the identities of individual nodes must be protected as well in mobile networks to avoid personal privacy concerns. This paper proposes ID-based private key revocation scheme and non-interactive key agreement scheme in anonymous MANETs. The proposed scheme provides the user privacy using pseudonyms and private key generation and revocation schemes with consideration of dynamic user changes. Therefore, our schemes can be applied in dynamic and privacy-preserving MANETs which are helpful to share multimedia data.
Mobile ad hoc networks (MANETs) are infrastructure-less, autonomous, and stand-alone wireless networks with dynamic topologies. Unlike conventional wireless networks, such as wireless cellular networks and wireless LANs, MANETs are rapidly deployable with self-organizing and self-maintaining capabilities. Because of the advantages of these features, MANETs usually refer to networks created for a special purpose. Recently, MANETs have been extended to cluster-based architectures to enhance the efficiency and security of MANETs. And this structure helps users in MANETs to share multimedia data efficiently [1 , 2]
However, MANETs are subject to various types of attacks because of the wireless and infrastructure-less environment. Moreover, these network structures make it difficult to apply conventional security mechanisms in MANETs directly. In traditional certificate-based cryptography (CBC), a user's public key is certified with a certificate, which is issued by a certification authority (CA). Even though it is feasible to support on-line public key infrastructure (PKI) services, the cost is very high, and this limits their application when the dynamic property and the poor connectivity are considered. As a powerful alternative to CBC, ID-based cryptography (IBC) [3 , 4] , which was proposed by Shamir, has been gaining momentum in recent years. This is enabled by a trusted private key generator (PKG), which issues a private key corresponding to each user's identity before users first join the networks. Recently, Boneh and Franklin [5] suggested spreading the PKG using threshold cryptography to counter key escrow problem. Research on distributed PKGs (D-PKGs) is applied to ad hoc networks, called cluster-based ad hoc networks [1 , 6] . Most studies about cluster-based MANETs have been based on hierarchy topology structures which classify nodes into two types, representative nodes, which perform the role of D-PKGs, called clusterheads (CHs), and common nodes.
This paper proposes an ID-based private key generation and revocation schemes for newly joining and leaving nodes. And we also proposes noninteractive key agreement scheme using key pairs of pseudonyms. Our schemes are compatible with anonymous cluster-based MANETs [7] and suitable for dynamic and practical MANETs.
The rest of the paper is organized as follows. In Section 2, we present preliminaries and review the anonymous cluster-based MANETs. In Section 3, we describe ID-based private key generation and revocation schemes for newly joining and leaving nodes. Finally, we analyze the security of the proposed scheme in Section 4 and have conclusions in Section 5.
In this section, we present cryptographic techniques and notations used as building blocks. Then we review the anonymous cluser-based MANET [7] .
- 2.1 ID-Based Cryptosystem
Recently IBC has its rapid development taken place due to the application of the pairing technique outlined below.
Let p,q be the large primes and E/Fp indicate an elliptic curve y 2 = x 3 + ax + b over the finite field Fp . We denote by G 1 a q-order subgroup of the multiplicative group of the finite field
PPT Slide
Lager Image
The discrete logarithm problem (DLP) is required to be hard in both G 1 and G 2 . For us, a pairing a map
PPT Slide
Lager Image
with the following properties:
  • Bilinear: ∀P,Q,R,S∈G1,
  • Non-degenerate: If P is a generator ofG1, thenis a generator ofG2
  • Computable: There is an efficient algorithm to computefor allP,Q∈G1.
Note that
PPT Slide
Lager Image
is also symmetric, i. e.,
PPT Slide
Lager Image
for all P,Q G 1 , which follows immediately from the bilinearity and the fact that G 1 is a cyclic group. Modified Weil [4] and Tate [8] pairing are examples of such bilinear maps for which the bilinear diffie-hellman problem (BDHP) is believed to be hard.
- 2.2 Threshold Scheme
Secret sharing schemes were independently introduced by the Blakley [9] and the Shamir [10] in 1979. They introduced a way to split a secret K into n shares. And only t or more than t shares among n can reconstruct a secret K. It is called (t,n)-secret sharing, denoted as (t,n)-SS.
Shamir's (t,n)-SS. Shamir's ( t,n )- SS is based on polynomial interpolation. The scheme consists of two algorithms:
  • ① Secret Sharing Generation. A trusted partyTdistributes shares of a secretKtonusers as follow:
  • Tchooses a primep> max(K,n), and definesα0=K.
  • Tpicks a polynomialf(x) of degree (t-1) randomly:f(x) =α0+α1x+ ...αt-1xt-1, in which the secretK=α0=f(0) and all coefficients (α0,...,αt-1) are in a finite fieldFp=GF(p) with p elements.
  • TcomputesKi=f(si) (mod p) for i=1,...,n. and securely transfer the sharesKito each user.
  • ② Secret Reconstruction. Any group of sizetor more thantcan reconstruct the polynomialf(x)
PPT Slide
Lager Image
PPT Slide
Lager Image
is called a Lagrange coefficient. The secret is recovered by f (0) = K .
For more information on this scheme, readers can refer to the original paper [10] .
- 2.3 Notations
Table 1 lists some important notations. whose concrete meanings will be further explained.
PPT Slide
Lager Image
- 2.4 Anonymous Cluster-Based MANETs
In this section, we review the anonymous cluster-based MANETs [7] . The network architecture of the anonymous cluster-based MANETs is illustrated on Fig. 1 . Each cluster is composed of a clusterheader (CH) and common nodes (users in Fig. 1 ).
PPT Slide
Lager Image
Cluster Configuration and Pseudonym Generation.
- 2.4.1 Configuration of clusters
Before the network is established, each CH has received secret sharings gm ( chj ), where 0 ≤ m U , 1 ≤ j n from the PKG. To recover a cluster key, CHs, at least t , gather their secret sharing at the same update phase m . Using these secret sharings, CHs can compute cluster key Km . And the initial secure channel between a CH and a user is established using their private/public key pairs. In here, the system cannot support user's anonymity, that is, adversaries can guess and find users what they want to attack.
- 2.4.2 Generation of pseudonyms
To generate pseudonyms for users within a cluster, each CH initially generates it's polynomial, called respective polynomial with a cluster key Km . And they generate pseudonyms for common nodes using their respective polynomials. Common nodes receive private/public key pairs of pseudonyms using channel previously established. By using these pseudonym key pairs, a CH and a user or between users can establish secure channels without exposing their real identities. The pseudonyms are generated as follows,
  • ① Generate respective polynomial. CHs have a same cluster keyKmby reconstructing polynomialgm(x). Each CH generates a respective polynomialby setting the cluster keyKmas a secret, This means that respective polynomials have same a secret
  • ② Generate pseudonym key pairs. The CH generates pseudonyms for common nodes within it's cluster using common nodes identities. For instance, the pseudonym ofIDAwithin the clusterCHjis constructed asAnd the public and private key pair is made asQPSA=PSAKmPandSPSA=PSA.
  • ③ Record pseudonyms. CHs record identities and corresponding pseudonyms at pseudonym lookup table (PLT)
  • ④ Share pseudonym key pairs. CHs then forward pseudonym key pairs to corresponding users using a secure channel established by initial private/public key pairs.
For more information on anonymous clusterbased MANETs, readers can refer to the original paper [7] .
In practical MANETs, new nodes which are not member of networks join networks and registered nodes at networks could leave networks frequently. Furthermore, some registered nodes could be compromised by adversaries. Therefore, the security system must provide private key generation for joining nodes and private key revocation for leaving or corrupted nodes. In this section, we propose private key generation and revocation schemes for newly joining and leaving nodes.
- 3.1 Private Key Generation for Newly Joining Nodes
Private key generations for newly joining nodes are same as [7] . Because of the property of threshold scheme, pseudonyms are generated by respective polynomials, the added private keys do not affect the security of system as long as newly joining nodes are uncorrupted ones and the networks can accept unbounded nodes academically. Thus we do not describe private key generation for newly joining nodes in detail in this paper.
- 3.2 Private Key Revocation for Leaving or Misbehaving nodes
In the anonymous security system using pseudonyms, each node can verify the validity of a pseudonym with a pair-wise key because only registered nodes who have received pseudonyms from CHs can have a group secret key SG . However, these registered nodes have the possibility of being subject to attacks and consequently could compromise the security of networks; therefore, the system should provide a priavate key revocation process to protect lasting attacks against those nodes. Y. Zhang et al. [11] proposed a key revocation using secret sharings. To provide node revocation, we modified their scheme to adopt to our system. Node revocation is carried out when more than Γ = {1,..., γ } misbehavior revocations are reported to a CH to protect innocent nodes against false accusations. The pseudonym revocation scheme is carried out as follows;
  • 1) Misbehavior Notification. To report a suspicious node whose public key isQPSxto aCHj, nodes perform the following:
  • ① Compute misbehavior notification. Node A detecting misbehavior of a suspicious node generates a misbehavior notification: {QpsA,QPSx,Ti} whereTiis the timestamp.
  • ② Forward the notification. Each node generating the misbehavior notification unicasts the notification toCHjusing a secure channel.
  • 2) Pseudonym Revocation. To revoke a reported node,CHjperforms the following:
  • ① Performs pseudonym revocation. When more thanγnotifications are collected on a CH,CHjperforms a secret reconstruction algorithm:
PPT Slide
Lager Image
PPT Slide
Lager Image
are called a Lagrange coefficient. Although the number of notifications is not as high as the number of t 1 , it works properly because CHk can generate arbitrary pseudonyms,
PPT Slide
Lager Image
  • ② Checks the validity of accusers. A CH can verify all accusers as legitimate nodes by comparingIf it does not hold, a CH knows that at least one of the accusers is incorrect and stops the pseudonym revocation.
  • ③ Revokes the identity of unlawful node. A CH recordsIDXto its credential revocation list (CRL)[12]and notifies to other CHsIDXas an unlawful node. Then a CH erasesIDXfrom PLT and stops updating it to isolate it from the networks.
  • ④ Publishes the pseudonym revocation. A CH publishes the pseudonym revocation to the networks:
  • 3) Revocation Verification. To verify the pseudonym revocation, every node in the networks performs the following:
  • ① Computes the revocation. Every node computesIf it holds, the nodes revoke the public keyQPSXand record it as unlawful. Then, all CHs change the update phase intom+ 1 and nodes update pseudonyms.
The revocation of a CH is similar to the process described above. If CHs (assume that nodes report a misbehaving CH to its CH) find a misbehaving CH, they report it to the revocation leader, one of the most powerful CHs, with their secret sharings. If the misbehavior notifications are more than γ , the revocation leader starts the revocation generation and computes gm ( x ). If gm (0) = Km , the revocation leader publishes the accused CH as a compromised CH, and then other CHs update the cluster key except the accused CH. Finally, the accused CH is isolated from the networks.
- 3.3 Non-interactive Key Agreement Scheme Using Pseudonyms
Key agreement is an essential process to exchange messages securely. The non-interactive key agreement scheme which happens under different clusters is the same as the scheme which happens under the same cluster, as long as the clusters are in the same update phase. We slightly modify the key agreement scheme in [7] . Our key agreement scheme with pseudonym between nodes is carried out as follows;
PPT Slide
Lager Image
In this section, we describe an analysis of our system with respect to security.
  • Non-manipulation.Our proposed security system ensure non-manipulation in case of at most (t-1 ort1-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. Adversaries should know the cluster keyKmto generate the pseudonym working correctly in networks and the respective polynomialto generate the pseudonym working correctly in a cluster. Thus, as long as (tort1) or more than (tort1) nodes and CHs are not colluding, non-manipulation is guaranteed.
  • Fundamental Security Services.Authentication of nodes and the confidentiality and integrity of messages are guaranteed by the non-interactive key agreement schemes. Each CH authenticates the nodes within a cluster by non-interactive key agreement using the initial key pair. For the proof, see e.g.,[13]. Authentication of the pseudonym and confidentiality and integrity of messages are guaranteed by non-interactive key agreement using pseudonyms. The pair-wise key is in the form ofH2(DAB||H3(SG)), whereActive outside/passive inside adversaries cannot generate a legitimate pseudonym of a specific node even though they have unspecific pseudonyms and identities. Furthermore, active outside adversaries do not know and compute the group secret key,SG. As a result, the non-interactive key agreement scheme using pseudonym is secure against active outside/passive insider adversaries.
Concerns for personal privacy and security in wireless environments are increasing rapidly as mobile devices are becoming more popular. Cluster-based MANETs are being considered to pioneer new markets; however, there are urgent unresolved security problems. Fundamental security services, such as authentication and key agreement, are challenging for secure security systems. Especially, private key update for newly joining and leaving or corrupted nodes should be supported considering dynamic topologies of MANETs. In addition, the protection of the user privacy becomes more important with wider use of wireless networks; therefore, the design of secure private key generation and revocation in privacy-preserving MANETs are required.
We presented private key generation and revocation schemes for privacy-preserving MANETs under practical assumptions. According to our protocol analysis, our proposed method provides most security requirements for dynamic MANETs by using the anonymity. Our schemes can be effectively applied in the dynamic environments with relatively better efficiency by using secret sharing schemes. Our proposed schemes improve security and widens the possible application area compared to previously proposed security systems. It could be usefully applied to preserve privacy in dynamic MANETs, where a trusted entity is not available. Such examples include military battlefields, emergency areas, mobile marketplaces, and VANETs.
YoHan Park
received B.S, M.S. and Ph.D. degrees from Kyungpook National University in 2006, 2008, and 2013 respectively. Currently, he is a lecturer in Kyungpook National University. His research interests are information security, mobile communication and network security.
YoungHo Park
received B.S, M.S. and Ph.D degrees from Kyungpook National Univeristy in 1989, 1991, and 1995 respectively. Currently, he is a professor in the School of Electronics Engineering at Kyungpook National University. His research interests are information security, network security, and mobile communication.
Li L. , Liu R. 2010 "Securing Cluster-Based Ad Hoc Networks with Distributed Authorities," IEEE Transactions on Wireless Communications 9 (10) 3072 - 3081    DOI : 10.1109/TWC.2010.080610.090759
Bechler M. , Hof H.J. , Kraft D. , Pahlke F. , Wolf L. "A Cluster-Based Security Architecture for Ad Hoc Networks," Proceeding of IEEE Infocom. 2004 2393 - 2403
Shamir A. "Identity-Based Cryptosystems and Signature Schemes," Proceeding of CRYP TO 84. LNCS 196 1984 47 - 53
Kang S.I. , Lee N.H. , Lee I.Y. 2009 "A Study on Group Key Management based on Mobile Device ID in Ad-hoc network," Journal of Korea Multimedia Society 12 (4) 540 - 549
Boneh D. , Franklin M. 2001 "Identity-Based Encryption from the Weil Pairing," Proceeding of CRYP TO 01. LNCS 2139 213 - 229
Zhang Y. , Liu W. , Lou W. , Fang Y. 2006 "Securing Mobile Ad Hoc Networks with Certificateless Public Keys," IEEE Transactions on Dependable and Secure Computing 3 (4) 386 - 399    DOI : 10.1109/TDSC.2006.58
Park Y.H. , Park Y.H. , Moon S.J. 2013 "Anonymous Cluster-Based MANETs with Threshold Signature," International Journal of Distributed Sensor Networks 1 - 9
Barreto P. , Kim H. , Bynn B. , Scott M. "Efficient Algorithms for Pairing-Based Cryptosystems," Proceeding of CRYP TO 02. LNCS 2442 2002 354 - 369
Blakley G.R. 1979 "Safeguarding Cryptographic Keys," American Federation of Information Processing Societies 79 313 - 317
Shamir A. 1979 "How to Share a Secret," Communication 22 (11) 612 - 613
Fang Y. , Zhu X. , Zhang Y. 2007 "Securing Resource-Constrained Wireless Ad Hoc Networks," IEEE Wireless Communications 16 16 (2) 24 - 30    DOI : 10.1109/MWC.2009.4907556
Raya M. , Hubaux J. 2007 "Securing Vehicular Ad Hoc Networks," Journal of Computer Security 15 (1) 39 - 68
Dupont R. , Enge A. 2006 "Provably Secure Non-Interactive Key Distribution based on Pairings," Discrete Applied Mathematic 154 (2) 270 - 276    DOI : 10.1016/j.dam.2005.03.024