Abstract
We consider a network where users can issue certificates that identify the public keys of other users in the network. The issued certificates in a network constitute a set of certificate chains between users. A user u can obtain the public key of other user v from a certificate chain from u to v in the network. For the certificate chain from u to v, u is called the source of the chain and v is called the destination of the chain. Certificates in each chain are dispersed between the source and destination of the chain such that the following condition holds. If any user u needs to securely send messages to any other user v in the network, then u can use the certificates stored in u and v to obtain the public key of v (then u can use the public key of v to set up a shared key with v to securely send messages to v). The cost of dispersing certificates in a set of chains among the source and destination users in a network is measured by the total number of certificates that need to be stored in all users. A dispersal of a set of certificate chains in network is optimal if no other dispersal of the same chain set has a strictly lower cost. In this paper, we show that the problem of computing optimal dispersal of a given chain set is NP-Complete. We also present three polynomial-time algorithms that compute optimal dispersals for three special classes of chain sets.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
McBurnett, N.: PGP web of trust statistics (1996), http://bcn.boulder.co.us/neal/pgpstat/
Rivest, R.L., Lampson, B.: SDSI – A simple distributed security infrastructure. Presented at CRYPTO 1996 Rumpsession (1996)
Boeyen, S., Howes, T., Richard, P.: Internet X.509 public key infrastructure operational protocols - LDAPv2. RFC 2559 (1999)
Myers, M., Ankney, R., Malpani, A., Galperin, S., Adams, C.: X.509 Internet public key infrastructure online certificate status protocol - OCSP. RFC 2560 (1999)
Ellison, C., Frantz, B., Lampson, B., Rivest, R., Thomas, B., Ylonen, T.: SPKI certificate theory. RFC 2693 (1999)
Blaze, M., Feigenbaum, J., Ioannidis, J., Keromytis, A.: The keynote trust-management system version 2. RFC 2704 (1999)
Clarke, D., Elien, J.E., Ellison, C., Fredette, M., Morcos, A., Rivest, R.: Certificate chain discovery in SPKI/SDSI. Journal of Computer Security 9, 285–322 (2001)
Elley, Y., Anderson, A., Hanna, S., Mullan, S., Perlman, R., Proctor, S.: Building certificate paths: Forward vs. reverse. In: Proceedings of the 2001 Network and Distributed System Security Symposium (NDSS 2001), pp. 153–160 (2001)
Freudenthal, E., Pesin, T., Port, L., Keenan, E., Karamcheti, V.: dRBAC: distributed rolebased access control for dynamic coalition environments. In: Proceedings of 22nd International Conference on Distributed Computing Systems (ICDCS 2002), pp. 411–420 (2002)
Li, N., Winsborough, W.H., Mitchell, J.C.: Distributed credential chain discovery in trust managemen. Jounal of Computer Security 11, 35–86 (2003)
Zhou, L., Haas, Z.J.: Securing ad hoc networks. IEEE Network 13, 24–30 (1999)
Kong, J., Zerfos, P., Luo, H., Lu, S., Zhang, L.: Providing robust and ubiquitous security support for wireless mobile networks. In: Proceedings of Ninth Internation Conference on Network Protocols (ICNP 2001), pp. 251–260 (2001)
Gouda, M.G., Jung, E.: Certificate dispersal in ad-hoc networks. In: Proceedings of the 24th International Conference on Distributed Computing Systems (ICDCS 2004), IEEE, Los Alamitos (2004)
Gouda, M.G., Jung, E.: Vulnerability analysis of certificate chains (2004) (in preparation)
Ajmani, S., Clarke, D.E., Moh, C.H., Richman, S.: Conchord: Cooperative sdsi certificate storage and name resolution. In: Druschel, P., Kaashoek, M.F., Rowstron, A. (eds.) IPTPS 2002. LNCS, vol. 2429, pp. 141–154. Springer, Heidelberg (2002)
Reiter, M.K., Stubblebine, S.G.: Resilient authentication using path independence. IEEE Transactions on Computers 47, 1351–1362 (1998)
Hubaux, J.P., Buttyán, L., Capkun, S.: The quest for security in mobile ad hoc networks. In: Proceedings of the 2001 ACM International Symposium on Mobile ad hoc networking & computing, pp. 146–155. ACM Press, New York (2001)
Capkun, S., Buttyán, L., Hubaux, J.P.: Self-organized public-key management for mobile ad hoc networks. IEEE Transactions on Mobile Computing 2, 52–64 (2003)
Jung, E., Elmallah, E.S., Gouda, M.G.: Optimal dispersal of certificate chains. In: Proceedings of IEEE Global Telecommunications Conference (Globecom 2004), IEEE, Los Alamitos (2004) (to appear)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2004 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Jung, E., Elmallah, E.S., Gouda, M.G. (2004). Optimal Dispersal of Certificate Chains. In: Guerraoui, R. (eds) Distributed Computing. DISC 2004. Lecture Notes in Computer Science, vol 3274. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-30186-8_31
Download citation
DOI: https://doi.org/10.1007/978-3-540-30186-8_31
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-23306-0
Online ISBN: 978-3-540-30186-8
eBook Packages: Springer Book Archive