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.
Keywords
Hash Tree, Ad Hoc Network, Authentication
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
