Apparatus and method for demonstrating and confirming the status of a digital certificates and other data

• US 6,532,540 B1
• Filed: 06/23/1998
• Issued: 03/11/2003
• Est. Priority Date: 05/14/1996
• Status: Expired due to Term

• Current Assignee: Axway Incorporated (Axway Software SA)
• Original Assignee: Valicert, Inc. (Axway Software SA)
• Inventors: Kocher, Paul Carl
• Primary Examiner(s): HUA, LY
• Assistant Examiner(s): DiLorenzo, Anthony
• Application Number:
  US09/103,656
• Time in Patent Office: 1,722 Days
• Field of Search: 713/158, 713/175, 713/156, 713/157, 713/176, 380/30
• US Class Current: 713/158
• CPC Class Codes: H04L 2209/30 Compression, e.g. Merkle-Damgard construction
• CPC Class Codes: H04L 2209/56 Financial cryptography, e.g. electronic payment or e-cash
• CPC Class Codes: H04L 9/3236 using cryptographic hash functions
• CPC Class Codes: H04L 9/3247 involving digital signatures
• 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

Methods and apparatuses for providing cryptographic assurance based on ranges as to whether a particular data item is on a list. According to one computer-implemented method, the items on the list are sorted and ranges are derived from adjacent pairs of data items on the list. Next, cryptographically manipulated data is generated from the plurality of ranges. At least parts of the cryptographically manipulated data is transmitted onto a network for use in cryptographically demonstrating whether any given data item is on the list. According to another computer-implemented method, a request message is received requesting whether a given data item is on a list of data items. In response, a range is selected that is derived from the pair of data items on the list that define the smallest range that includes the given data item. A response message is transmitted that cryptographically demonstrates whether the first data item is on the list using cryptographically manipulated data derived from the range. According to another computer-implemented method, a request message requesting an indication as to whether a first data item is on a list of data items is transmitted. In response, a message is received that cryptographically demonstrates whether the first data item is on the list, where the response message identifies a range that is derived from the pair of data items on the list that defines the smallest range that includes the first data item.

Claims

1. A computer implemented method comprising:

selecting data that is derived from less than all the entries on a list identifying revoked digitally signed data items, wherein said data identifies whether at least a particular digitally signed data item has been revoked, and wherein said data is cryptographically manipulated in a manner that provides a relative level of assurance to third parties that said data was supplied by an entity responsible for supplying revocation status information;

transmitting said data to an owner of the particular digitally signed data item;

the owner transmitting said data to a plurality of third parties; and

said plurality of third parties confirming whether the particular digitally signed data item has been revoked using said data.

2. The method of claim 1, further comprising:

selecting an expiration indicator that identifies when the representation of revocation status identified by the data expires;

transmitting said expiration indicator with said data to said owner;

the owner transmitting said expiration indicator with said data to said

plurality of third parties; and

said plurality of third parties checking the representation of revocation status identified by said data has not expired using said expiration indicator.

3. The method of claim 1, wherein said digitally signed data items are digital certificates.

4. The method of claim 1, wherein said digitally signed data items are signed code.

5. The method of claim 1, wherein said entity is a certifying authority that issued said digitally signed data items.

6. The method of claim 1, further comprising:

said entity receiving said list from a certifying authority that issued said digitally signed data items; and

said entity deriving said cryptographically manipulated data from said list.

7. The method of claim 6, further comprising:

said entity transmitting said data over a network to a confirmation issuer; and

said confirmation issuer performing said steps of selecting said data and transmitting said data to said owner.

8. The method of claim 7, wherein said confirmation issuer is not a trusted server.

9. The method of claim 6, wherein said list is a certificate revocation list.

10. The method of claim 1, wherein said selecting said data comprises:

selecting a range that is derived from the pair of entries on said list that defines the smallest range that includes said particular digitally signed data item; and

deriving said data from said range.

11. The method of claim 10, wherein said deriving said data from said range comprises:

selecting a digitally signed representation of the range as part of said data.

12. The method of claim 10, said deriving said data from said range comprises:

determining, for a tree having leaf nodes that represent ranges derived from the entries on said list, a path through said tree from said selected range to a root node of said tree; and

deriving said data from said path.

13. The method of claim 12, wherein said deriving said data from said path comprises:

including in said data information identifying said selected range;

including in said data a set of nodes from said tree that cryptographically bind the selected range to said root node; and

including in said data a digitally signed representation of said root node.

14. The method of claim 13, wherein said including in said data said set of nodes comprises:

including those nodes in said set of nodes that are not on the path through the tree and that allow a holder thereof to derive the nodes in said set of nodes in the path.

15. The method of claim 1, wherein said selecting comprises:

determining, for a tree having nodes formed from the entries on the list, a path through said tree from the entry on the list representative of said particular digitally signed data item to a root node of said tree; and

deriving said data from said path.

16. The method of claim 1, further comprising:

the owner transmitting a request message to said entity requesting revocation status information regarding said particular digitally signed data item.

17. A computer implemented method comprising:

receiving a request message from an owner of a digitally signed data item requesting revocation status information regarding the digitally signed data item;

selecting data that is derived from less than all the entries on a list identifying revoked digitally signed data items, wherein said data identifies whether at least the digitally signed data item has been revoked, and wherein said data is cryptographically manipulated in a manner that provides a relative level of assurance to third parties that said data was supplied by an entity responsible for supplying revocation status information;

forming a response message that includes said data; and

transmitting said response message to said owner for distribution to third parties.

18. The method of claim 17, further comprising:

selecting an expiration indicator that identifies when the representation regarding the revocation status identified by the data expires; and

forming said response message to also include said expiration indicator.

19. The method of claim 17, wherein said digitally signed data items are digital certificates.

20. The method of claim 17, wherein said digitally signed data items are signed code.

21. The method of claim 17, wherein said entity is a certifying authority that issued said digitally signed data items.

22. The method of claim 17, wherein said entity received said list from a certifying authority that issued said digitally signed data items.

23. The method of claim 22, wherein said list is a certificate revocation list.

24. The method of claim 17, further comprising:

a confirmation issuer receiving over a network from said entity information representative of said data; and

said confirmation issuer performing the steps of receiving said request message, selecting said data, forming said response message, and transmitting said response message.

25. The method of claim 24, wherein said entity received said list from a certifying authority that issued said digitally signed data items.

26. The method of claim 25, wherein said list is a certificate revocation list.

27. The method of claim 24, wherein said confirmation issuer is not a trusted server.

28. The method of claim 17, wherein said selecting said data comprises:

selecting a range that is derived from the pair of entries on said list that defines the smallest range that includes said particular digitally signed data item; and

deriving said data from said range.

29. The method of claim 28, wherein said deriving said data from said range comprises:

selecting a digitally signed representation of the range as part of said data.

30. The method of claim 28, wherein said deriving said data from said range comprises:

determining, for a tree having leaf nodes that represent ranges derived from the entries on said list, a path through said tree from said selected range to a root node of said tree; and

deriving said data from said path.

31. The method of claim 30, wherein said deriving said data from said path comprises:

including in said data information identifying said selected range;

including in said data a set of nodes in said tree that cryptographically bind the selected range to said root node; and

including in said data a digitally signed representation of said root node.

32. The method of claim 31, wherein said including said set of nodes comprises:

including those nodes in said set of nodes that are not on the path through the tree and that allow a holder thereof to derive the nodes in said set of nodes on the path.

33. The method of claim 17, wherein said selecting comprises:

determining, for a tree having nodes formed from the entries on the list, a path through said tree from the entry on the list representative of said particular digitally signed data item to a root node of said tree; and

deriving said data from said path.

34. A computer implemented method comprising:

selecting relative to a particular digitally signed data item a set of entries on a list identifying revoked digitally signed data items, wherein said set of entries identifies whether said particular digitally signed data item has been revoked, wherein the set of entries does not include all entries on the list;

selecting data that is derived from the set of entries selected for said digitally signed data item and that is cryptographically manipulated in a manner that provides a relative level of assurance to third parties that a trusted source supplied the data;

selecting an expiration indicator that identifies when the representation of revocation status identified by the data expires;

forming a response message that includes said data and said expiration indicator; and

transmitting said response message to an owner of that digitally signed data item for distribution to third parties.

35. The method of claim 34, wherein the set of entries includes two entries.

36. The method of claim 34, wherein said digitally signed data items are digital certificates.

37. The method of claim 34, wherein said digitally signed data items are signed code.

38. The method of claim 34, wherein said trusted source is a certifying authority that issued said digitally signed data items.

39. The method of claim 34, wherein said trusted source is an entity that receives said list from a certifying authority that issued said digitally signed data items.

40. The method of claim 39, wherein said list is a certificate revocation list.

41. The method of claim 34, further comprising the preliminary step of:

a confirmation issuer receiving over a network information representative of said list and said data, said confirmation issuer performing the remaining steps of the method.

42. The method of claim 41, wherein said confirmation issuer received the information from said trusted source, and said trusted source received said list from a certifying authority that issued said digitally signed data items, and said trusted source generated said data.

43. The method of claim 41, wherein said confirmation issuer is not a trusted server.

44. The method of claim 34, wherein said selecting the set of entries comprises:

selecting a range that is derived from the pair of entries on said list that defines the smallest range that includes said particular digitally signed data item.

45. The method of claim 44, wherein said selecting said data comprises:

selecting a digitally signed representation of the range as part of said data.

46. The method of claim 44, wherein said selecting the set of entries comprises:

determining, for a tree having leaf nodes that represent ranges derived from the entries on said list, a path through said tree from said selected range to a root node of said tree; and

deriving said data from said path.

47. The method of claim 46, wherein said deriving said data comprises:

including in said data information identifying said selected range;

including in said data a set of nodes in said tree that cryptographically bind the selected range to said root node; and

including in said data a digitally signed representation of said root node.

48. The method of claim 47, wherein said including said set of nodes comprises:

including those nodes in said set of nodes that are not on the path through the tree and that allow a holder thereof to derive the nodes in said set of nodes on the path.

49. The method of claim 34, wherein said selecting said data comprises:

determining, for a tree having nodes formed from the entries on the list, a path through said tree from the entry on the list representative of said particular digitally signed data item to a root node of said tree; and

deriving said data from said path.

50. A computer implemented method comprising:

an owner of a digitally signed data item forming a first message requesting revocation status information regarding the digitally signed data item;

the owner transmitting said first message to a confirmation issuer that supplies revocation status information;

the owner receiving a second message from said confirmation issuer that includes data that was derived from less than all the entries on a list identifying revoked digitally signed data items, wherein said data identifies whether at least the digitally signed data item has been revoked, and wherein said data has been cryptographically manipulated in a manner that provides a relative level of assurance that the data was provided by a trusted source; and

the owner transmitting said data to a plurality of third parties.

51. The method of claim 50, wherein the owner transmits along with said data the digitally signed item.

52. The method of claim 50, wherein said data also includes an expiration indicator that identifies when the representation of revocation status identified by the data expires.

53. The method of claim 50, wherein said digitally signed data items are digital certificates.

54. The method of claim 50, wherein said digitally signed data items are signed code.

55. The method of claim 50, wherein said trusted source is a certifying authority that issued said digitally signed data items.

56. The method of claim 50, wherein said data was generated by said trusted source responsive to receiving said list from a certifying authority that issued said digitally signed data items.

57. The method of claim 56, wherein said list is a certificate revocation list.

58. The method of claim 56, said confirmation issuer received a message over a network from said trusted source identifying said data.

59. The method of claim 58, wherein said confirmation issuer is not a trusted server.

60. The method of claim 56, wherein said confirmation issuer and said trusted source are the same entity.

61. The method of claim 50, wherein said data is derived from a range that was derived from the pair of entries on said list that defines the smallest range that includes said digitally signed data item.

62. The method of claim 61, wherein said data includes a digitally signed representation of the range.

63. The method of claim 61, wherein said data was derived from a path through a tree from said selected range to a root node of said tree, said tree having leaf nodes that represent ranges derived from the entries on said list.

64. The method of claim 63, wherein said data includes information identifying said selected range, a set of nodes in said tree that cryptographically bind the selected range to said root node, and a digitally signed representation of said root node.

65. The method of claim 63, wherein said set of nodes includes those nodes in said set of nodes that are not on the path through the tree from the selected range to said root node, but excluding at least some nodes that are on the path.

66. The method of claim 50, wherein said data was derived from a path through a tree from a leaf node representative of said digitally signed data item to a root node of said tree, said tree having leaf nodes formed from the entries on the list.