How to avoid the breakdown of public key infrastructures: forward secure signatures for certificate authorities

Recent attacks and publications have shown the vulnerability of hierarchical Public Key Infrastructures (PKIs) and the fatal impact of revoked Certification Authority (CA) certificates in the PKIX validity model. Alternative validity models, such as the extended shell and the chain model, improve the situation but rely on independent proofs of existence, which are usually provided using time-stamps. As time-stamps are validated using certificates, they suffer from the same problems as the PKI they are supposed to protect. Our solution to this problem is abandoning time-stamps and providing proof of existence using Forward Secure Signatures (FSS). In particular, we present different possibilities to use the chain model together with FSS, resulting in schemes that include the necessary proofs of existence into the certificates themselves.