Public-key certificate management system and method

1. A method for authenticating a digital certificate comprising the steps of:

providing a database of digital certificates stored within a computer storage media accessible by a computer, wherein each of the digital certificates are stored using both a first data structure in which items are stored in chronological order and a second data structure which is ordered by certificate identifier;

using the first data structure to establish a proof that a later snapshot of the database is an extension of an earlier snapshot of the database; and

using the second data structure to establish a proof that a given digital certificate is currently valid; and wherein:

the first data structure is arranged such that proofs of chronological extension of the data structure can be furnished in a time of the order of the logarithm of its size; and

the second data structure is arranged such that proofs of a set of keys in the data structure corresponding to a given certificate identifier can be furnished in a time of the order of the logarithm of its size.

2. The method of claim 1 , wherein the first and/or second data structures comprise tree data structures.

3. The method of claim 1 , wherein the first data structure comprises a Merkle tree.

4. The method of claim 1 , wherein, in the second data structure, a list of keys is stored for each certificate, of which only the last one is the current one, the others being revoked.

5. The method of claim 1 , wherein the database may be updated by marking a certificate as revoked.

6. The method claim 1 , comprising providing to a third party a proof that a later snapshot of the database is an extension of an earlier snapshot of the database; and/or a proof that a given digital certificate is currently valid.

7. The method of claim 1 , wherein the step of providing a database of digital certificates is carried out by a certificate prover (CP) who is independent of a party who issues the digital certificates.

8. The method of claim 1 , comprising the step of verifying consistency between data stored in the first and second data structures so as to perform a consistency check, and wherein the consistency check is carried out by an auditor who is independent of users whose digital certificates are stored in the database, of the CP and of a party who issues the digital certificates.

9. The method of claim 1 , comprising the step of verifying consistency between data stored in the first and second data structures so as to perform a consistency check, by querying a randomly chosen portion or portions of the data structures.

10. The method of claim 9 , wherein a result of the consistency check and/or the proof that a later snapshot of the database is an extension of an earlier snapshot of the database and/or the proof that a given digital certificate is currently valid is represented as one or more graphical elements and/or graphical effects which are displayed to a user.

11. The method of claim 10 , wherein the graphical elements comprise a series of traffic light icons, which are selectively colored according to the status of the consistency check.

12. The method of claim 10 , wherein the graphical effects comprise the selective coloring of an electronic messaging service address according to the status of the one or more of the consistency check, proof that a later snapshot of the database is an extension of an earlier snapshot of the database and proof that a given digital certificate is currently valid.

13. The method of claim 1 , wherein the certificate identifier comprises an electronic messaging service address; and the steps of querying the first data structure to establish a proof that a later snapshot of the database is an extension of an earlier snapshot of the database and querying the second data structure to establish a proof that a given digital certificate is currently valid are performed by a message sender to authenticate a digital certificate of a message recipient before sending an electronic message encrypted with the recipient's public key.

14. A system for authenticating a digital certificate comprising:

a database of digital certificates stored within a computer storage media accessible by a computer, wherein each of the digital certificates are stored using both a first data structure in which items are stored in chronological order and a second data structure which is ordered by certificate identifier; and

executable functionality that queries the first data structure to establish a proof that a later snapshot of the database is an extension of an earlier snapshot of the database; and that queries the second data structure to establish a proof that a given digital certificate is currently valid; and wherein:

the first data structure is arranged such that proofs of chronological extension of the data structure can be furnished in a time of the order of the logarithm of its size; and

the second data structure is arranged such that proofs of a set of keys in the data structure corresponding to a given certificate identifier can be furnished in a time of the order of the logarithm of its size.

15. The system of claim 14 , further comprising executable functionality that marks a certificate as revoked.

16. The system of claim 14 , wherein the database and executable functionality that queries the database are hosted by a certificate prover (CP); who also provides an interface for third parties to request and receive the proof that a later snapshot of the database is an extension of an earlier snapshot of the database; and the proof that a given digital certificate is currently valid.

17. A computer program product comprising:

a database stored within a computer storage media accessible by a computer, comprising:

a first data structure in which items are stored in chronological order; and

a second data structure which is ordered by user identifier; and

executable functionality that queries the first data structure to establish a proof that a later snapshot of the database is an extension of an earlier snapshot of the database; and that queries the second data structure to establish a proof that a given datum is currently valid; and wherein:

the first data structure is arranged such that proofs of chronological extension of the data structure can be furnished in a time of the order of the logarithm of its size; and

the second data structure is arranged such that proofs of a set of keys in the data structure corresponding to a given certificate identifier can be furnished in a time of the order of the logarithm of its size.