Optimally-balanced Hash Tree Generation in Ad Hoc Networks
Main Article Content
Abstract
Ideally a hash tree is a perfect binary tree with leaves equal to power of two. Each leaf node in this type of tree can represent a mobile node in an ad hoc network. Each leaf in the tree contains hash value of mobile node’s identification (ID) and public key (PK). Such a tree can be used for authenticating PK in ad hoc networks. Most of the previous works based on hash tree assumed perfect hash tree structures, which can be used efficiently only in networks with a specific number of mobile nodes. Practically the number of mobile nodes may not be always equal to a power of two and the conventional algorithms may result in an inefficient tree structure. In this paper the issue of generating a hash tree is addressed by proposing an algorithm to generate an optimally-balanced structure for a complete hash tree. It is demonstrated through both the mathematical analysis and simulation that such a tree is optimally-balanced and can efficiently be used for public key authentication in ad hoc networks.
Article Details
Issue
Section
Prootcols, Algorithms and Applications
Copyright for articles published in this journal is retained by the authors, with first publication rights granted to the journal. By virtue of their appearance in this open access journal, articles are free to use, with proper attribution, in educational and other non-commercial settings. A Copyright Form should be downloaded by authors and must be faxed to the AJICT before the publication of their manuscripts will be scheduled.
References
R. C. Merkle, "Protocols for Public Key Cryptosystems," in Proc. IEEE Symposium on Research in Security and Privacy, 1980.
W. Du, R. Wang, and P. Ning, "An Efficient Scheme for Authenticating Public Keys in Sensor Networks," ACM, MobiHoc, 2005. L. Zhou and C. V. Ravishankar, "Dynamic Merkel Trees for verifying privileges in Sensor Networks," in Proc. IEEE ICC 2006.
M. Jakobsson and S. Wetzel, "Efficient Attribute Authentication with Applications to Ad hoc Networks," ACM, VANET, 2004.
V. Kondratieva and S-W Seo, "Optimized Hash Tree for Authentication in Sensor Networks," IEEE Communications Letters, Vol. 11, No. 2, Feb. 2007.
ns-2 : Network Simulator, available at http://www.isi.edu/nsnam
OpenSSL : Standard Cryptographic Library, available at http://www.openssl.org
W. Du, R. Wang, and P. Ning, "An Efficient Scheme for Authenticating Public Keys in Sensor Networks," ACM, MobiHoc, 2005. L. Zhou and C. V. Ravishankar, "Dynamic Merkel Trees for verifying privileges in Sensor Networks," in Proc. IEEE ICC 2006.
M. Jakobsson and S. Wetzel, "Efficient Attribute Authentication with Applications to Ad hoc Networks," ACM, VANET, 2004.
V. Kondratieva and S-W Seo, "Optimized Hash Tree for Authentication in Sensor Networks," IEEE Communications Letters, Vol. 11, No. 2, Feb. 2007.
ns-2 : Network Simulator, available at http://www.isi.edu/nsnam
OpenSSL : Standard Cryptographic Library, available at http://www.openssl.org