skip to main content
10.1145/1143549.1143559acmconferencesArticle/Chapter ViewAbstractPublication PagesiwcmcConference Proceedingsconference-collections
Article

Modeling key agreement in multi-hop ad hoc networks

Published: 03 July 2006 Publication History

Abstract

Securing multicast communications in ad hoc networks has become one of the most challenging research directions in the areas of wireless networking and security. This is especially true as ad hoc networks are emerging as the desired environment for an increasing number of civilian, commercial and military applications, also addressing an increasingly large number of users. In this paper we study a very basic security question for Ad Hoc Networks: Key Agreement against passive adversaries. Despite being a widely studied area in wired networks, the problem becomes significantly more challenging for ad hoc networks, and even more for sensor networks, due to lack of trusted entities, infrastructures, full connectivity, routing structures, and due to severe limitations on the resources and capabilities of network nodes. In this paper we perform a comprehensive investigation of Key Agreement over resource constrained ad hoc networks. First, we formally model the key agreement problem over multi-hop ad hop networks, and we directly extend known key agreement protocols for wired networks, and evaluate the efficiency of such approaches. We then go beyond natural extensions of such protocols, by proposing non-trivial extensions based on efficient topology-driven simulations of logical networks over an arbitrary physical network, in order to optimize the most significant metrics of interest for such networks: i.e. bandwidth, latency, processing cost. Indeed, the resulting protocols are significantly more efficient in some or all of the above metrics, as our analytical results indicate.

References

[1]
M. Steiner, G. Tsudik G, M. Waidner, Diffie-Hellman Key distribution extended to groups. 3d ACM Conf. on Computer & Communication Security, ACM Press, 1996, 31-37.
[2]
W.Diffie, M.Hellman, New directions in cryptography, IEEE Transactions on Information Theory, 22 (1976), 644--654.
[3]
M. Burmester, Y. Desmedt. A Secure and Efficient Conference Key Distribution System. Advances in Cryptology- EUROCRYPT '94, Lecture Notes in Computer Science. Springer-Verlag, Berlin Germany, 1994.
[4]
I. Ingemarsson, D. Tang, C. Wong. A Conference Key Distribution System. IEEE Transactions on Information Theory, 28(5):714--720, Sept. 1982
[5]
F.T. Leighton. Introduction to Parallel Algorithms and Architectures, Morgan Kauffman, 1992
[6]
M. Harchol, T. Leighton, D. Lewin. Resource discovering in distributed networks. Procs 15th, ACM Symp., on Principles of Distributed Computing, May 1999, 229--237
[7]
S. Kutten, D. Peleg. Deterministic distributed resource discovery. In 19th annual ACM SIGOPS symp. on Principles of Distributed Computing, Portland, OR, 16--19 July 2000.
[8]
R. Gallager, P. Humblet, P. Spira. A distributed algorithm for minimum-weight spanning trees. ACM Transactions on Programming Languages and Systems (TOPLAS), 5(1): 66--77, January 1983
[9]
C. Cheng, I. Cimet, S. Kumar. A protocol to maintain a minimum spanning tree in a dynamic topology. In symp. Procs' on Communication architectures and protocols, 330--337, ACM Press, 1988
[10]
A. Mooij, W. Wesselink. A formal analysis of a dynamic distributed spanning tree algorithm. Computer Science TR 03-16, Technische Universiteit Eindhoven, Dec. 2003
[11]
S. Dolev, A. Israeli, S. Moran. Self-stabilization of dynamic systems assuming only read/write atomicity. Distributed Computing, 7:3--16,1993.
[12]
L. Blin, F. Butelle. The first approximated distributed algorithm for the minimum degree spanning tree problem on general graphs. Int'l Parallel and Distributed Processing Symposium (IPDPS'03), p. 161a.
[13]
F. Gärtner, A Survey of Self-Stabilizing Spanning-Tree Construction Algorithms, EPFL Technical Report, 2003.

Cited By

View all
  • (2008)A Clustering-based Group Key Agreement Protocol for Ad-Hoc NetworksElectronic Notes in Theoretical Computer Science (ENTCS)10.1016/j.entcs.2008.05.005192:2(43-53)Online publication date: 1-May-2008

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
IWCMC '06: Proceedings of the 2006 international conference on Wireless communications and mobile computing
July 2006
2006 pages
ISBN:1595933069
DOI:10.1145/1143549
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 03 July 2006

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. approximation algorithms
  2. efficiency
  3. group key agreement
  4. optimization
  5. performance evaluation
  6. topology driven protocols

Qualifiers

  • Article

Conference

IWCMC06
Sponsor:

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)1
  • Downloads (Last 6 weeks)0
Reflects downloads up to 20 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2008)A Clustering-based Group Key Agreement Protocol for Ad-Hoc NetworksElectronic Notes in Theoretical Computer Science (ENTCS)10.1016/j.entcs.2008.05.005192:2(43-53)Online publication date: 1-May-2008

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media