Simplifying Dynamic Public Key Certificate Graph for Certification Path Building in Distributed Public Key Infrastructure

Blockchain technology brings the decentralization of a single point of failure to a Public Key Infrastructure (PKI). We presented Meta-PKI that establishes the trust relationships among certificate authorities (CAs) for a decentralized PKI. In a decentralized PKI where trust relationships among CAs change dynamically, it is challenging to discover the certification path between two CAs because a public key certificate graph can be complex and huge. Here we propose certification path building on Meta-PKI by partition-based approach. The proposed method simplifies the public key certificate graph by constructing partitions based on the trustworthiness of certificates. It is experimentally shown that the simplified graph reduces the exponential growth of the processing time for certificate path building.