International Association
for Cryptologic Research

This paper examines the vulnerabilities inherent in prevailing Public Key Infrastructure (PKI) systems reliant on centralized Certificate Authorities (CAs), wherein a compromise of the CA introduces risks to the integrity of public key management. We present PKChain, a decentralized and compromise-tolerant public key management system built on blockchain technology, offering transparent, tamper-resistant, and verifiable services for key operations such as registration, update, query, validation, and revocation. Our innovative approach involves a novel threshold block validation scheme that combines a novel threshold cryptographic scheme with blockchain consensus. This scheme allows each validator to validate each public key record partially and proactively secures it before inclusion in a block. Additionally, to further validate and verify each block and to facilitate public verification of the public key records, we introduce an aggregate commitment signature scheme. Our contribution extends to the development of a new, efficient, and practical Byzantine Compromise-Tolerant and Verifiable (pBCTV) consensus model, integrating the proposed validation and signature schemes with practical Byzantine Fault Tolerance (pBFT). Through a comprehensive examination encompassing security analysis, performance evaluation, and a prototype implementation, we substantiate that PKChain is a secure, efficient, and robust solution for public key management.