Optimal Dispersal of Certificate Chains



A user u can obtain the public key of other user v from a certificate chain from u to v in the network. Certificates in each chain are dispersed among the source and destination nodes of the chain such that the following condition holds. If any node u needs to securely send messages to any other node v in the network, then u can use the certificates stored in u and v to obtain the public key of v. The cost of dispersing certificates of chains is measured by the number of certificates that need to be stored in the nodes. A certificate dispersal of chains in the network is optimal if no other dispersal has a strictly lower cost. In this paper, we show that to find an optimal dispersal of given chains is NP-Complete and present three polynomial-time algorithms which compute optimal dispersals of chains in three special classes.