Dispersability and vulnerability analysis certificate systems

textA certificate is a way to distribute public keys of users in a distributed system. For example, in the current Internet, certificates are heavily used in SSL/TLS for securing e-commerce. In this thesis, we describe the three phases of a certificate, how a certificate is issued, used, and revoked/expired. In particular, we propose a new way of distributing certificates, called certificate dispersal. Certificate dispersal assigns certificates to users such that when a user u wants to securely communicate with another user v in a system, users u and v may find out the public key of user v based on the certificates stored in u or v. In other words, users u and v have no need to contact any other user in the system. We define dispersal in two environments, a certificate graph and a certificate chain set and the costs of dispersal. In the environment of certificate chain set, computing an optimal dispersal is NP- complete. However, we identify several classes of chain sets and certificate graphs for which optimal dispersal an be computed in polynomial-time. For each class we present an algorithm that computes an optimal dispersal. We also analyze the vulnerability of certificate systems. Any certificate system suffer from impersonation attacks when a private key of a user is revealed to an adversary. We define the metric called vulnerability that measures the s ope of damage when some private keys are revealed, and show how different certificate systems have different vulnerabilities. These results can be used to design a good certificate system that satisfies system requirements of dispersal cost and vulnerability.Computer Science