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

• US 7,526,644 B2
• Filed: 03/01/2005
• Issued: 04/28/2009
• Est. Priority Date: 05/14/1996
• Status: Expired due to Fees

• Current Assignee: Axway Incorporated (Axway Software SA)
• Original Assignee: Axway Incorporated (Axway Software SA)
• Inventors: Kocher, Paul Carl
• Primary Examiner(s): Moise, Emmanuel L
• Assistant Examiner(s): Teslovich, Tamara
• Application Number:
  US11/069,687
• Publication Number:
  US 20050198497A1
• Time in Patent Office: 1,519 Days
• Field of Search: 713155-158, 713175-176, 709/232
• 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/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 readable medium that encodes (i) only a selected subportion of a tree and (ii) a digitally signed root node thereof for use in cryptographically demonstrating whether a given data item is represented in said tree, the computer readable encoding made by a method comprising the steps of:

sorting a plurality of data items belonging to a superset thereof;

deriving a plurality of ranges using adjacent pairs of data items in said sorted plurality of data items as endpoints such that all data items in said plurality of data items are at endpoints of said plurality of ranges and such that all other data items in said superset fall in-between the endpoints of said plurality of ranges;

generating a hash tree having leaf nodes that represent the plurality of ranges;

digitally signing a root node of said tree; and

encoding said digitally signed root node and said selected subportion of said tree for supply in the computer readable medium.

2. The computer readable encoding made by the method of claim 1, wherein said step of generating said tree includes the step of forming leaf nodes from endpoints of said plurality of ranges.

3. The computer readable encoding made by the method of claim 2, wherein said step of generating said tree includes the step of forming an adjacent pair of leaf nodes from different endpoints of one of said plurality of ranges.

4. The computer readable encoding made by the method of claim 1, wherein said step of generating said tree includes the step of forming each of a plurality of the leaf nodes from the endpoints of a different one of said plurality of ranges.

5. The computer readable encoding made by the method of claim 1, wherein said plurality of data items identify digital certificates sharing an attribute.

6. The computer readable encoding made by the method of claim 5, wherein said attribute is that the digital certificates are revoked.

7. The computer readable encoding made by the method of claim 1, wherein said plurality of data items identify digital signatures.

8. The computer readable encoding made by the method of claim 1, wherein said plurality of data items identify digital signatures on binary code.

9. The computer readable encoding made by the method of claim 1, wherein said plurality of data items identify revoked credit cards.

10. A computer readable medium that encodes a response message, the computer readable encoding made by a method comprising the steps of:

receiving a request message requesting whether a first data item is one of a plurality of data items belonging to a superset of data items;

selecting a range that is derived from a pair of data items in said plurality of data items that defines the smallest range that includes said first data item, wherein the first data item is not one of the plurality of data items if the first data item is in-between the endpoints of the selected range, and wherein the first data item is one of said plurality of data items if said first data item is on one of the endpoints of the selected range;

determining, for a tree having leaf nodes that represent ranges derived from adjacent pairs of said plurality of data items in a sorted list of said plurality of data items, a path through said tree from said selected range to a first of a set of root nodes; and

generating the response message and supplying an encoding thereof in the computer readable medium, the response message including;

data identifying said selected range in said response message,

a set of nodes in said tree such that each node in said set of nodes and at least a previously identified node on said path can be combined to identify a previously unidentified node on said path, until said first root node is identified, the set of nodes excluding at least certain nodes on the path from the response message, and

a digitally signed representation of the first root node in said response message.

11. The computer readable encoding made by the method of claim 10, wherein the endpoints of the selected range are independently hashed and then hashed together to generate a node in the tree.

12. The computer readable encoding made by the method of claim 10, wherein each leaf node specifies one of one range, an endpoint of one range, a hashed range, and a hashed endpoint of one range.

13. The computer readable encoding made by the method of claim 10, wherein said plurality of data items identify digital certificates sharing an attribute.

14. The computer readable encoding made by the method of claim 13, wherein said attribute is that the digital certificates are revoked.

15. The computer readable encoding made by the method of claim 10, wherein said plurality of data items identify digital signatures.

16. The computer readable encoding made by the method of claim 10, wherein said plurality of data items identify digital signatures on binary code.

17. The computer readable encoding made by the method of claim 10, wherein said plurality of data items identify revoked credit cards.

18. A program product encoded in one or more computer readable media for installation on computer configurable to (i) transmit a request message as to whether a first data item is one of a plurality of data items belonging to a superset of data items and to (ii) receive a response message that includes a digitally signed representation submitted to be a root node of a tree having leaf nodes that represent ranges, the ranges derived from adjacent pairs of data items in a sorted list of said plurality of data items, data identifying the range that includes said first data item, and a set of nodes in said tree sufficient to generate said root node starting from said range, the computer program product comprising:

software executable on the computer to determine if said first data item is one of said plurality of data items based on said range, wherein the first data item is not one of the plurality of data items if the first data item is in-between the endpoints of the selected range, and wherein the first data item is one of said plurality of data items if said first data item is on one of the endpoints of the selected range;

the software further executable to generate said root node using said range and the set of nodes and to determine if said received digitally signed representation matches said root node.

19. The computer program product of claim 18,

wherein said set of nodes includes nodes that together with a node on a path from the range to the root node can be used to generate a next node on the path, but excluding at least some nodes that are on the path.

20. The computer program product of claim 18, wherein each leaf node specifies one of one range, an endpoint of one range, a hashed range, and a hashed endpoint of one range.