## Optimal Dispersal of Certificate Chains

### Authors

- Eunjin Jung, The University of Texas at Austin
- Ehab Elmallah, University of Alberta
- Mohamed Gouda, The University of Texas at Austin

### Abstract

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.