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

• US 5,903,651 A
• Filed: 05/14/1996
• Issued: 05/11/1999
• 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): Hayes, Gail O.
• Assistant Examiner(s): SAYADIAN, HRAYR
• Application Number:
  US08/645,759
• Time in Patent Office: 1,092 Days
• Field of Search: 380/23, 380/25
• 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 method comprising the computer implemented steps of:

where each digital certificate in a superset of issued digital certificates is associated with a unique data item, sorting those data items associated with a plurality of revoked digital certificates belonging to said superset of issued digital certificates;

deriving a plurality of ranges using adjacent pairs of data items in said sorted data items as endpoints such that all data items associated with said plurality of revoked digital certificates are at endpoints of said plurality of ranges and such that all data items associated with unrevoked digital certificates fall in-between the endpoints of said plurality of ranges, wherein each adjacent pair of data items in said sorted data items is used to derive a different one of said pluralitv of ranges;

digitally signing each of the plurality of ranges individually, wherein the plurality of ranges and said digital signatures cryptographically demonstrate whether any given digital certificate is one of said plurality of revoked digital certificates; and

electronically transmitting said plurality of ranges and said said digital signatures onto a network and using them in cryptographically demonstrating whether any given digital certificate is one of said plurality of revoked digital certificates, wberein a given one of said pilrality of ranges together with the digital signature of that range cryptographically demonstrates whether a given digital certificate within that range is one of the plurality of revoked digital certificates.

2. The method of claim 1, further comprising the step of:

hashing at least the serial number from each of the plurality of revoked digital certificates to generate said unique data items.

3. A method comprising the computer implemented steps of:

receiving a request message requesting whether a first digital certificate is one of a plurality of revoked digital certificates belonging to a superset of issued digital certificates, where each digital certificate in said superset of issued digital certificates is associated with a unique data item;

selecting a range having as endpoints the unique data items associated with the pair of revoked digital certificates in said plurality of revoked digital certificates that defines the smallest range of the unigue data items that includes said first digital certificate, wherein the first digital certificate is not one of the plurality revoked digital certificates if the unique data item associated with the first digital certificate is in-between the endpoints of the range, and wherein the first digital certificate is revoked if the unique data item associated with the first digital certificate is one of the endpoints of the range;

forming a response message including the unique data items that are the endpoints of the range and including a digital signature on the range, said response message cryptographically demonstrating whether said first digital certificate is one of said plurality of revoked digital certificates; and

electronically transmitting the response message onto a network.

4. The method of claim 3, wherein ranges are derived from adjacent pairs of data items in a sorted list of the data items associated with said plurality of revoked digital certificates.

5. The method of claim 3, wherein said digital signature is on the endpoints of the selected range independently hashed and then hashed together.

6. The method of claim 3, wherein said digital signature is on the endpoints of the selected range hashed together.

7. The method of claim 3, wherein said digital signature is on the endpoints of the selected range independently hashed and then concatenated.

8. A method comprising the computer implemented steps of:

electronically transmitting a request message as to whether a first digital certificate is one of a plurality of revoked digital certificates belonging to a superset of issued digital certificates, where each digital certificate in said superset of issued digital certificates is associated with a unigue data item;

receiving a response message that cryptographically demonstrates whether said first digital certificate is one of said plurality of revoked digital certificates, said response message identifying a range having as endpoints the data items associated with the pair of revoked digital certificates in said plurality of revoked digital certificates that defines the smallest range of the data items that includes said first digital certificate, said response message also including a digital signature on said range, wherein the first digital certificate is not one of the plurality of revoked digital certificates if the unique data item associated with the first digital certificate is in-between the endpoints of the range, and wherein the first digital certificate is revoked if the unigue data item associated with the first digital certificate is one of the endpoints of the range; and

determining if said first digital certificate is one of said plurality of revoked digital certificates based on said range by,

detemining whether the unique data item associated with said first digital certificate is either in-between the endpoints of said range, one of the endpoints of said range, or outside said range, and

validating said digital signature.

9. The method of claim 8, wherein said range is derived from an adjacent pair of data items in a sorted list of the data items that identify said plurality of revoked digital certificates.

10. The method of claim 8, wherein said digital signature is on the endpoints of said range independently hashed and then concatenated.

11. The method of claim 8, wherein the unique data item associated with each digital certificate is a hash of at least the serial number from that digital certificate.