Paper 2019/807

When PKI (finally) met Provable Security

Hemi Leibowitz, Amir Herzberg, and Ewa Syta


Public Key Infrastructure (PKI) schemes were first proposed in 1978 and standardized in 1988, yet, unlike most cryptographic schemes, PKI schemes were never rigorously defined. Achieving provable security for PKI is necessary and long overdue, as PKI provides the foundation for important applications of public key cryptography, such as TLS/SSL. In response, we present the first precise specifications of a secure PKI scheme, suitable for a variety of PKI designs. PKI schemes have significantly evolved since X.509, with more complex goals, e.g., transparency, to ensure security against corrupt issuers. In addition to the basic PKI properties, our definitions encompass these more recent and advanced aspects. Our results have important implications. First, our specifications allow a better scrutiny and comparison of the multitude of new PKI designs recently proposed, such as Google’s Certificate Transparency (CT) and related PKIs, as well as future designs. Second, the specifications facilitate proper analysis of protocols and systems that use PKI, such as TLS/SSL, code signing, IPsec, DNSSEC, RPKI, BGPsec, permissioned blockchains, voting, recommendations, which is of critical importance as most real-world security schemes inherently rely on PKI. Finally, we use our specifications to formalize and prove X.509 version 2 PKI, showing that provable security is achievable for ‘real’ PKI designs.

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 ( - CTng: Secure Certificate and Revocation Transparency (

Available format(s)
Public-key cryptography
Publication info
Preprint. MINOR revision.
public-key infrastrcturecertificates
Contact author(s)
leibo hemi @ gmail com
amir herzberg @ gmail com
ewa syta @ trincoll edu
2021-09-29: last of 6 revisions
2019-07-14: received
See all versions
Short URL
Creative Commons Attribution


      author = {Hemi Leibowitz and Amir Herzberg and Ewa Syta},
      title = {When PKI (finally) met Provable Security},
      howpublished = {Cryptology ePrint Archive, Paper 2019/807},
      year = {2019},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.