Tree-based certificate revocation system

• US 6,301,659 B1
• Filed: 11/26/1997
• Issued: 10/09/2001
• Est. Priority Date: 11/02/1995
• Status: Expired due to Term

• Current Assignee: Assa Abloy AB
• Original Assignee: Silvio Micali
• Inventors: Micali, Silvio
• Primary Examiner(s): Barron, Jr., Gilberto
• Assistant Examiner(s): KABAKOFF, STEPHEN ERIC
• Application Number:
  US08/979,983
• Time in Patent Office: 1,413 Days
• Field of Search: 713/156, 713/157, 713/158
• US Class Current: 713/158
• CPC Class Codes: G06Q 20/02 involving a neutral party, e.g. certification authority, notary or trusted third party [TTP]
• CPC Class Codes: H04L 2209/30 Compression, e.g. Merkle-Damgard construction
• CPC Class Codes: H04L 2209/60 Digital content management, e.g. content distribution
• CPC Class Codes: H04L 9/3236 using cryptographic hash functions
• CPC Class Codes: H04L 9/3268 using certificate validation, registration, distribution or revocation, e.g. certificate revocation list [CRL]
• CPC Class Codes: H04L 9/50 using hash chains, e.g. blockchains or hash trees

Abstract

A method and system for overcoming the problems associated with certificate revocation lists (CRL'"'"'s), for example, in a public key infrastructure. The invention uses a tree-based scheme to replace the CRL.

Claims

1. A method for using at least one Merkle tree to authenticate revocation status about a plurality of certificates, comprising:

(a) generating a plurality of values, wherein each of the values indicates that at least one of the certificates has been revoked and wherein for each certificate, there is at least one value indicating status of the certificate;

(b) constructing at least one Merkle tree containing on a plurality of its nodes at least one of the plurality of values indicating whether at least one of the certificates has been revoked; and

(c) authenticating, with a digital signature, a root node of the at least one Merkle tree to provide an authenticated root.

2. A method according to claim 1, wherein the digital signature is verifiable by an end user.

3. A method according to claim 1, wherein the values indicate which certificates have been revoked.

4. A method according to claim 3, wherein the values include a date of revocation for the certificates that have been revoked.

5. A method according to claim 1, wherein the values indicate which certificates are valid.

6. A method according to claim 1, wherein the values include a date of issue for the certificates that have been issued.

7. A method according to claim 1, wherein the values indicate which certificates have been revoked and which certificates are valid.

8. A method according to claim 1, wherein the values indicate which certificates have been revoked and which certificates have been issued.

9. A method according to claim 1, wherein the values indicate which certificates are valid and which certificates have been issued.

10. A method according to claim 1, wherein the values indicate which certificates have been revoked, which certificates are valid, and which certificates have been issued.

11. A method according to claim 1, wherein at least one of the values corresponds to more than one certificate.

12. A method according to claim 11, wherein the values include a date of issue for the certificates that have been issued.

13. A method according to claim 1, wherein certificate information determines locations of the values within the Merkle tree.

14. A method according to claim 1, wherein positions of the values within the Merkle tree provide information about certificates corresponding thereto.

15. A method according to claim 14, wherein the information includes serial numbers for each of the certificates.

16. A method according to claim 1, wherein the values correspond to serial numbers of the certificates.

17. A method according to claim 16, wherein the certificate values correspond to serial numbers of the certificates combined with additional information.

18. A method according to claim 1, wherein the authenticated root contains additional information.

19. A method according to claim 18, wherein the additional information includes date information.

20. A method according to claim 18, wherein the additional information includes an indication of at least one of:

revoked, issued, and valid for describing certificate information corresponding to the values of the Merkle tree.

21. A method according to claim 1, wherein the values indicating status of certificates are leaf nodes of the Merkle tree.

22. A method, according to claim 1, further comprising:

introducing dummy items.

23. A method, according to claim 22, wherein the number of dummy items that is introduced plus the number of other items is a power of two.