Name
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 another 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 a 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. Thus, minimizing the total number of certificates stored in all users is NP--complete. We identify three special classes of chain sets that are of practical interests and devise three polynomial-time algorithms that compute optimal dispersals for each class. We also present two polynomial-time extensions of these algorithms for more general classes of chain sets. |
Year | DOI | Venue |
|---|---|---|
2004 | 10.1109/TPDS.2007.1007 | IEEE Trans. Parallel Distrib. Syst. |
Keywords | Field | DocType |
security and protection,certificate graph,certificate chain,np-complete problem,public-key management.,computational complexity,authentication,optimal dispersal,security and privacy protection,internet,public key cryptography,certification,polynomial-time algorithm,telecommunication security,message authentication,certificate dispersal,public key,polynomial time | Computer security,Computer science,Computer network,Time complexity,Public-key cryptography,Minimum time,Biological dispersal,Distributed computing,Certificate,Polynomial method | Conference |
Volume | Issue | ISSN |
18 | 4 | 1045-9219 |
Citations | PageRank | References |
8 | 0.56 | 20 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Eunjin Jung | 1 | 125 | 13.06 |
| Ehab S. Elmallah | 2 | 105 | 19.29 |
| Mohamed G. Gouda | 3 | 1982 | 317.23 |