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

• US 20050198497A1
• Filed: 03/01/2005
• Published: 09/08/2005
• Est. Priority Date: 05/14/1996
• Status: Active Grant

• Current Assignee: Paul Carl Kocher
• Original Assignee: Paul Carl Kocher
• Inventors: Kocher, Paul Carl
• Granted Patent: US 7,526,644 B2
• Time in Patent Office: Days
• 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 method comprising the computer implemented steps of:

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

deriving a plurality of ranges using adjacent pairs of data items in said sorted plurality of data items as endpoints such the all data items in said plurality of the data items are an 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 the tree; and

electronically transmitting said digitally signed root node and parts of said tree onto a network for use in cryptographically demonstrating whether a given data item is one of said plurality of data items.