Paper 2019/807

Provable Security for PKI Schemes

Abstract

PKI provides a critical foundation to applied cryptographic protocols. However, there are no rigorous security specifications for PKI, and therefore, no PKI schemes were proven secure. This is problematic considering the extensive reliance on PKI, the multiple failures of PKI systems, and the fact that some proposed and deployed PKI schemes have complex design and advanced goals. The lack of specifications and proofs for PKI schemes means that applied cryptographic systems that use PKI are analyzed by adopting overly simplified models of the PKI, often, simply assuming secure public keys. We present game-based security specifications for PKI schemes, and prove the security of the two most important and widely deployed schemes: PKIX and Certificate Transparency (CT), both based on version 3 of the X.509 standard, and using the (standard) CRL revocation mechanism. The proof shows a reduction from an adversary that `wins' the PKI-specifications game to an adversary that `wins' against the underlying signature scheme or hash function. This is the first reduction-based definition and proof of security for a realistic PKI scheme.

Note: Some of the work that was initially included in previous versions of this work resulted in separate publications. Namely: - MoSS: Modular Security Specifications Framework (https://eprint.iacr.org/2020/1040) - CTng: Secure Certificate and Revocation Transparency (https://eprint.iacr.org/2021/818)