Implementation of Threshold Cryptography in MANETS

DOI : 10.17577/IJERTV3IS10349

Download Full-Text PDF Cite this Publication

Text Only Version

Implementation of Threshold Cryptography in MANETS

P. Swetha

Associate Professor, Computer Science & Engineering Department, JNTUHCEJ, Andhra Pradesh, India,


Security is the most desirable feature in Mobile Ad hoc NETworks (MANET). In order to have secured communication between two parties, a secret key is used for encrypting and decrypting messages. The communication in a mobile network can be protected by ensuring that a secret key can be known only to the two communicating parties. The distribution of the secret key can be achieved by a Cryptographic technique called Threshold Cryptography (TC). In this technique, the secret key is divided into multiple shares, where these shares are distributed to the nodes participating in the communication in an infrastructure less network. In TC, another module Proactive Secret Sharing (PSS) is introduced, which allows the set of nodes to refresh the shares by generating a new set of shares without reconstructing the secret key. TC along with PSS provides essential security by not exposing the secret key.

Index Terms: MANET, Threshold Cryptography, Proactive Secret Sharing, Share refreshment, Lagranges Interpolation.

  1. Introduction

    guidelines In wireless communication, a Mobile Adhoc NETwork (MANET) is an emerging area for new developments. Security in a MANET, is an important issue which is ruling the internet world today. A MANET is a network which provides wireless communication between heterogeneous devices with least or no infrastructure [1]. A MANET is a self-configuring network which dynamically adapts a temporary network topology for establishing a internetwork for communication between people and devices without any preexisting infrastructure. Each node participating in communication provides services such as message forwarding, authentication, routing information etc. for creating a temporary network. A route for forwarding data packets is established between arbitrary nodes for sending and receiving packets. The legitimate nodes must establish a secure communication channel to thwart against threats, eavesdrops or tampering of the data. Due to the unique characteristics of MANET such as dynamic topology, infrastructure less wireless network, it is mandatory to provide security [2]. Implementing a secure ad hoc network has become a challenging task because of the vulnerabilities and limited computational and storage capabilities. Hence, the basic security requirements of MANET are availability, authentication, integrity, confidentiality, authorization. With all these constraints, the most critical and complex issue is the distribution of a secret

    group key to the legitimate nodes in a secure fashion which is used to encrypt the data.

    Considering the nature and challenges posed by the MANET and to provide security, Threshold Cryptography (TC) is employed. TC is a cryptographic technique, sharing secret among legitimate nodes [3]. In TC, a secret key is divided into shares using a cryptographic operation and these shares are distributed to the nodes participating in communication. The secret can be reconstructed only when the threshold number out of shares are combined together. The individual shares alone cannot serve the purpose of reconstructing the original secret key. A secret group key cannot be constructed with fewer than shares.

    The basic requirement is that, within the share transmission procedure, each share must not be disclosed. However there is a possibility for a malicious node to generate the secret key by stealing or more shares from the participating nodes, within long span of time. In order to escape from the threats of exposing a secret key, a Proactive Secret Sharing (PSS) can be introduced. PSS plays an important role as the key management protocol using threshold cryptography. In PSS, each share is updated periodically, such that a malicious node cannot construct the secret key within the short time span [4] [5]. In non-proactive secret sharing, if the threshold number of shares are compromised during the lifetime of the secret, the secret is compromised. In PSS scheme, all shares are refreshed by generating a new set of shares for the same secret key from the old shares and then the old shares are discarded after the each share is refreshed. All shareholders must cooperate with the PSS procedure for the protocol consistency.

    This paper presents TC implementation using PSS. The paper is organized as follows, section II discusses about the analysis of TC. Section III about the analysis of PSS protocol. Section IV about the simulation and results and finally section V concludes the paper with its future scope.

  2. Threshold Cryptography

    MANETs are susceptible to attacks because of the use of wireless links. The network confidentiality is violated when eavesdroppers are successful in accessing the secret information. The security services like availability, integrity, authentication and non-repudiation are violated when hackers try to attack the network to delete packets, or inject erroneous packets or impersonate a node. Compromised nodes launch attacks from within a network. The routings algorithms like on-demand and link-state algorithms fail to protect the data or sensitive routing information [6]. A centralized entity or a single node in a MANET is not

    trustworthy which could lead to vulnerabilities. For this, a security solution based on the distribution of trust is required. TC is used to distribute the trust to an aggregation of nodes.

    In TC scheme, a secret key is divided into shares and shared among nodes using some cryptographic operation. Any node can collect threshold number of

    shares and can reconstruct the original key [7]. On contrary, it is infeasible for at most nodes to construct the key even by collusion. A degree

    polynomial is constructed with the constant secret key

    and random elements:

    In this case, each of the shares is a pair of of numbers such that , where ,

    . Given shares, the secret key is computed using Lagranges Interpolation. Therefore, TC is one of the techniques suitable for MANETs in key sharing and distributing to multiple nodes because (1) it does not need any key infrastructure, (2) it works even in a busy network, where atleast nodes must reside in the same network. Hence, TC scheme can be defined as a concrete key management system in a MANET environment with one secret group key and its degree polynomial. Here,

    shareholders must be able to perform the cryptographic operation for the distribution of the trust. If a new node wishes to join the secure group communication, it must collect or more shares from the share-holders to generate the secret group key . The new node has to be authenticated before the transmission of the shares from each share-holder. The distribution of the shares among the nodes is achieved through a secure link with the help of Private/Public keys [8] where the nodes are certified by Certificate Authority (CA) [9]. The new node has to construct the secret group key without the knowledge of pre- used polynomial. The secret group key and the polynomial have to be securely initialized.

    The share-generation can be defined as a three -step process:

    1. Pick random coefficients .

    2. Build a polynomial of degree such that

      where is the secret key.

    3. Each participant receives a unique share and its .

      In order to generate the secret key, the pairs are collected from participants to rebuild the polynomial.

  3. li>

    Proactive Secret Sharing

A countermeasure to mobile adversaries, who can reconstruct a secret key within long time span, is the

proposal of proactive schemes. A Proactive TC uses share refreshment technique in which the participating nodes in collaboration must refresh their shares from the old shares. The newly refreshed shares constitute a new TC. After refreshing, the old shares are discarded and the new shares are used. Now the adversary cannot combine old shares with the new shares to generate the secret key. Hence, the challenging task to the adversary is to compromise nodes between periodic refreshing.

3.1 Share Refreshment Algorithm

Without using any key infrastructure, TC gives a way to convey a shared key to a node which is suitable for secret sharing in MANETs. However, given shares in TC, the secret can be found. The major shortcoming of TC is that, if a malicious node has stolen shares, within finite span of time, the original secret key can be generated. Therefore, share refreshment becomes necessary component, to refresh each share from the old ones without reconstructing the secret key [12]. For the share refreshment, each shareholder generates their own sub- shares and distributes these sub-shares to other participating nodes through a secure link, to refresh their own shares.

Algorithm Steps:

  1. Let a secret key be divided into shares

    with node having and distributed to nodes.

  2. Each node having , generates their own subkeys

  3. Every subkey is distributed to node through secure link.

  4. When node gets the subkey it,

    refresh the old share to new shares as

    After generating the new , the old share is discarded.

  5. Now, the new shares are are an sharing of the secret key , because , for all

After the PSS procedure, each node holds the refreshed shares where the old shares become useless. In this case, the malicious node must collect atleast shares before the refreshment which becomes impossible.

The block diagram for Threshold cryptography using PSS is shown. It is clearly depicted that first a secret key K is randomly generated which is divided and distributed among nodes. Later, if all nodes agrees for share refreshment , PSS procedure is started. After successful completion of PSS procedure, a node has to collect shares and generate the secret key .

Fig.3.1 : Flow Chart of Threshold Cryptography using PSS

The PSS procedure has to be initiated with proper timing coordination i.e., all shareholders must synchronize with the PSS procedure. Otherwise, if a node A starts PSS and other node B does not start PSS procedure , then node A receives old shares of B and B receives new shares of

A i.e., they exchange inconsistent shares, there by the secret key cannot be generated. Hence, it leads to protocol inconsistency. Therefore, it is assumed that all share-holders start the PSS procedure with proper timing coordination.


Fig -3.2 shows the share refreshment procedure. Assume a secret key is divided into four , , which are distributed to the nodes A,B,C,D respectively. Each of these shares in turn are divided into sub-shares by their respective nodes. . Node A generates the subkeys

from . Similarly nodes B,C and D also generates the subkeys ,

, from , ,

respectively. Every subkey is distributed to node as given in step3 of the algorithm. When node receives the sub-share it, refresh the old share to new shares as

After producing the new shares, old shares become obsolete. Now these new shares are used for distribution among other nodes.

  1. Implementation

    In this section, TC along with PSS implementation is discussed. The evaluation was conducted using Network Simulator-2[13]. The code for creating a wireless network topology is done in TCL language. The nodes were created using wireless links and provide routing algorithm to route the data to the corresponding destination. The size of the simulation area is 700×700 with at most 100 nodes. The encryption is done by using DES symmetric encryption along with AODV protocol[14].

    The following parameters are assumed given in Table:1:



    Number of Nodes


    Threshold Value


    Routing protocol


    Wireless simulation area


    Channel type


    Mac type


    Simulation duration

    600 Units


    User Data


    k2 B

    k4 k3

    C D

    Fig -3.2: Share Refreshment Procedure

    Table-1: List of parameters

    Threshold cryptography with Proactive secret sharing is run in ns-2 and the simulation is shown in Network Animator (NAM) [15][16][17]. After execution the simulation will generate key shares and they are distributed to other nodes for key refreshment.

    We get the following interface.

    Fig-4.1: NAM output showing mobile nodes and the terminal showing key exchange between nodes

    In Fig 4.1, the Network Animator displays 10 mobile nodes. The terminal window displays each node receiving subkeys from other nodes.

    Fig-4.2: Key refreshment

    In the Fig 4.2, it shows the encrypted text transmitted from source to the destination. Source sending its subkeys to the other nodes. Later, each node refreshes their respective keys.

    Fig-4.3: Destination received the key shares

    Fig 4.3 displays that destination receives subkeys from other nodes and constructs the original key. This generated key will be used for decrypting the message received from the source. Fig 4.4 and Fig 4.5 displays the same i.e., key exchange and key refreshment process in the Network animator.

    Fig-4.4: Nodes receiving the keys

    Fig-4.5: Keys are refreshing and sending their shares to corresponding nodes

    The simulation can be run for 50 to 100 nodes. But as the number of nodes increases the , the key generation and refreshment slows down since it increases the time complexity for key exchanges among all the nodes.

  2. Conclusion

    This paper focuses on analyzing Threshold Cryptography which protects from the direct exposure of secret key which is used for encryption and decryption of packets. Proactive secret sharing acts as an add-on to TC by refreshing the sub shares periodically by which a malicious node cannot construct the original secret key from the old sub shares. This is an efficient technique which helps to enforce the security in a mobile network. TC along with PSS can defend against most of the security attacks because the secret key itself is partitioned into multiple subshares. This technique works efficiently only when all the nodes are synchronized to start up PSS procedure. If not, a refreshed subshare cannot be generated. Developing novel synchronization procedures for the PSS protocol consistency would be the future work. Additional work can be done by appending a hash value to the secret key for the integrity and investigate the network performance as the mobile nodes increases.

  3. References

[1]. A. Mishra and K. M. Nadkarni, "Security in wireless adhoc networks – A Survey"', in The Handbook of Ad HocWireless Networks, M. Ilyas, Ed. Boca Raton: CRC Press, 2002.

[2]. G.S. Mamatha, Dr. S. C. Sharma, A Highly Secured Approach against Attacks in MANETS , International Journal of Computer Theory and Engineering, Vol. 2, No. 5, October, 2010


[3]. A. Shamir, "How to share a secret," Communication of the ACM, vol.22, 1979.

[4]. A. Herzberg, J. Stanislaw, H. Krawczyk, M. Yung, Proactive Secet Sharing or: How to Cope with Perpetual Leakage, Proc. 15th Annual International Cryptology Conference on Advances in Cryptology, 1995, pp. 339-352.

[5]. A. Herzberg, S. Jarecki, H. Krawczyk, and M. Yung. Proactive secret sharing or: How to cope with perpetual leakage. In D. Coppersmith, editor, Advances in CryptologyCrypto95, the 15th Annual International Cryptology Conference, Santa Barbara, CA USA, August 2731, 1995, Proceedings, volume963 of Lecture Notes in Computer Science. Springer, 1995.

[6]. Neha Gupta, Manish Shrivastava, Securing Routing Protocol by Distributed Key Management and Threshold Cryptography in Mobile Ad hoc Network , International Journal of Advanced Computer Research (ISSN (print): 2249-7277 ISSN (online): 2277- 7970) Volume-3 Number-1 Issue-9 March-2013.

[7]. Marianne A. Azer, Magdy S. El-Soudani, Threshold Cryptography and Authentication in Ad Hoc Networks -Survey and Challenges , Second International Conference on Systems and Networks Communications (ICSNC 2007),0-7695-2938-0/07 IEEE

, 2007.

[8]. Y. Kitada, A. Watanabe, K. Takemori, and I. Sasase, On demand distributed public key management for wireless ad hoc network in IEEE Pacific Rim Conference on Communication, Computers and Signal Processing, 2005.

[9]. H.Mohri, I. Yasuda, Y. Takata, and H. Seki, Certificate chain discovery in web of trust for ad hoc networks, in proceeding of the 21st International Conference on Advanced Information Networking and Applications workshop, IEEE Computer Society, vol.2,pp,2007.

[10]. T-79.159 Cryptography and Data Security, 24.03.2004 Lecture 9: Secret Sharing, Threshold Cryptography,

MPC, Helger Lipmaa , pg no.11-20. [11]…/lectures


[12]. Hitoshi Asaeda, Musfiq Rahman, Yoshihiro Toyama,

Structuring Proactive Secret Sharing in Mobile Ad -hoc Networks

,0-7803-9410-0/06,2006 IEEE.

[13]. T. Issariyakul and E. Hossain, Introduction to Network Simulator NS2, Springer 2008.

[14]. C. Perkins, E. Belding-Royer and S. Das, Ad hoc On- Demand Distance Vector (AODV) Routing, RFC3561, July 2003. [15]. ns-2 Home page :


[17]. Tutorial for the Network Simulator ns by Marc Greis.

Leave a Reply