Paper Info
Title
Optimal dispersal of special certificate graphs
Abstract
We consider a network where nodes can issue certificates that identify the public keys of other nodes in the network. The issued certificates in a network constitute a directed graph, called the certificate graph of the network. The issued certificates are dispersed among the network nodes such that the following condition holds. If any node, u, needs to send messages to any other node, v, in the network, then u can use the certificates stored in both u and v to obtain the public key of v (then u can securely send messages to v). The cost of a dispersal which assigns certificates to the nodes of a network is measured by the average number of certificates that need to be stored in one node. A dispersal is optimal if its cost is minimum. We present three algorithms and show that each algorithm computes optimal dispersals for a rich class of certificate graphs. The time complexity of each of these algorithms, when one of the algorithms is used to disperse the certificates from a given certificate graph, is O(n2), where n is the number of nodes in the input certificate graph.
Year
DOI
Venue
2004
10.1109/GLOCOM.2004.1378402
Global Telecommunications Conference, 2004. GLOBECOM '04. IEEE
Keywords
Field
DocType
computational complexity,computer networks,directed graphs,public key cryptography,telecommunication security,computer network,directed graph,message sending,network nodes,public keys,secure communication,special certificate graphs,time complexity
Public key infrastructure,Computer science,Node (networking),Computer network,Directed graph,Theoretical computer science,Time complexity,Public-key cryptography,Biological dispersal,Certificate,Computational complexity theory
Conference
Volume
ISSN
ISBN
4
1930-529X
0-7803-8794-5
Citations 
PageRank 
References 
1
0.36
10
Authors
3
Name
Order
Citations
PageRank
Eunjin Jung112513.06
Elmallah, E.S.2275.32
Mohamed G. Gouda31982317.23