Revocation of cryptographic digital certificates

Abstract

Different targets (c 0 , N 1 ) of a digital certificate are mapped into a “super-target” using methods allowing a certificate validity verifier ( 110 ) to compute the super-target. The certificate includes the super-target instead of the targets. Also, a certificate with multiple targets can be signed with a redactable signature by the certification authority (CA 120 ). When the certificate's owner provides the certificate to a verifier together with a validity proof, the owner redacts the certificate to delete unnecessary targets. A single validity proof (c i (F)) may be provided to certificate owners for a set (F) of the certificates via a multicast transmission if a multicasting group ( 2010 ) is formed to correspond to the set. A verifier ( 110 ) may decide to cache the validity proof for a set provide the cached proof to other parties. The caching decision is based on the caching priority of the set F. The priority may depend on the number of certificates in the set F, the sum of the remaining validity periods for the certificates in the set, and other factors. In the setup phase, the CA generates validation proof data structures for greater time than the maximum validity period of any certificate. Therefore, new certificates can be added to the existing data structures after the setup phase. A distributed certificate authority includes a CA and a number of Sub-CAs ( 2610 ). The Sub-CAs have secret certificate validation data, but different data are provided to different Sub-CAs for each certificate. If a Sub-CA is compromised, the Sub-CA validity proof will be withheld by the CA to alert the verifiers not to use the data from this Sub-CA. Also, the secret data are encrypted when distributed to the Sub-CAs. A decryption key (DK.j.k) for each “partition” of time is distributed to each Sub-CA at or shortly before the start of the partition. A compromised Sub-CA can be reactivated at the end of the partition because the adversary does not get the decryption keys for the future partitions.

1 . A transmission method comprising transmitting, in an electromagnetic carrier wave, one or more computer instructions operable to cause a computer system to generate computer data comprising a validity or invalidity proof for a first digital certificate certifying that a cryptographic key is associated with an entity, the computer data comprising:
 (a1) period data for a period of time, for computing a first target, wherein the period of time is one of a plurality of periods of time each of which is associated with period data, and the first target is computable, in computer-implemented computation, from the period data associated with any one the periods of time;   wherein for each set in at least the first plurality, the period data form at least part of a hash tree, each period of time corresponding to the hash tree's node comprising the period data for the period of time, different periods of time corresponding to different nodes, wherein for at least two of the periods of time, one of the corresponding nodes is neither a child nor a parent of the other one of the corresponding nodes;   (a2) second target computation data for computing, in computer-implemented computation, a second target from the first target, wherein the second target is a function of a plurality of first targets each of which is associated with a set comprising the first digital certificate.   
     
     
         2 . The network transmission method of  claim 1  wherein for at least one set in the first plurality, for the nodes corresponding to at least two of the periods of time, one of the nodes is a parent of the other one of the nodes in the corresponding hash tree. 
     
     
         3 . A transmission method comprising transmitting, in an electromagnetic carrier wave, a computer program comprising one or more computer instructions operable to cause a computer system to generate computer-readable computer data for computer-implemented verification of validity and/or invalidity of one or more cryptographic digital certificates including a first digital certificate, each digital certificate certifying that a cryptographic key is associated with an entity, the computer data being for proving to a verifier computer system the validity or invalidity of at least the first digital certificate, the computer data comprising:
 (a) first data defining a plurality of sets, the plurality of sets comprising a first plurality of sets, wherein the first digital certificate belongs to each set in the first plurality;   (b) for each set in at least the first plurality, second data which define period data for each of a plurality of periods of time and also define a first target for the set, wherein the first target is computable, in computer-implemented computation, from the period data for any one of said periods of time by the verifier computer system to verify the validity and/or invalidity of any certificate in the set relative to the respective period of time;   wherein for each set in at least the first plurality, the period data form at least part of a hash tree, each period of time corresponding to the hash tree's node comprising the period data for the period of time, different periods of time corresponding to different nodes, wherein for at least two of the periods of time, one of the corresponding nodes is neither a child nor a parent of the other one of the corresponding nodes;   (c) third data defining a second target computable, in computer-implemented computation, from the first targets of the first plurality of sets.   
     
     
         4 . The network transmission method of  claim 3  wherein the first digital certificate does not include at least one of the first target values of the sets of the first plurality. 
     
     
         5 . The network transmission method of  claim 3  wherein for at least one set in the first plurality, for the nodes corresponding to at least two of the periods of time, one of the nodes is a parent of the other one of the nodes in the corresponding hash tree. 
     
     
         6 . The network transmission method of  claim 3  wherein the first digital certificate includes the second target. 
     
     
         7 . A transmission method comprising transmitting, in an electromagnetic carrier wave, one or more computer instructions operable to cause a computer system to perform a computer implemented proof operation for providing proofs of validity and/or invalidity of one or more cryptographic digital certificates including a first digital certificate, each digital certificate certifying that a cryptographic key is associated with an entity, the proof operation comprising:
 (a) receiving over a network:
 (a1) first data associating the first digital certificate with a first plurality of sets, wherein the first digital certificate belongs to each set in the first plurality; 
 (a2) data defining a first target for each set of the first plurality and defining a second target computable, in computer-implemented computation, from the first targets of the first plurality of sets; 
   (b) periodically receiving over a network, for each set in at least the first plurality, period data for each of a plurality of periods of time, wherein the first target is computable, in computer-implemented computation, from the period data for any one of the periods of time by a verifier computer system to verify the validity and/or invalidity of any certificate in the set relative to the respective period of time;   wherein for each set in at least the first plurality, the period data form at least part of a hash tree, each period of time corresponding to the hash tree's node comprising the period data for the period of time, different periods of time corresponding to different nodes, wherein for at least two of the periods of time, one of the corresponding nodes is neither a child nor a parent of the other one of the corresponding nodes;   (c) in each period of time, providing, if requested, a proof of validity or invalidity for at least the first digital certificate, the proof comprising the period data for the period of time and also comprising data for computer-implemented computation of the second target from the first target defined by the period data provided in said proof.   
     
     
         8 . The network transmission method of  claim 7  wherein for at least one set in the first plurality, for the nodes corresponding to at least two of the periods of time, one of the nodes is a parent of the other one of the nodes in the corresponding hash tree. 
     
     
         9 . A transmission method comprising transmitting, in an electromagnetic carrier wave, one or more computer instructions operable to cause a computer system to perform a verification operation for verifying a validity or invalidity of a first digital certificate certifying that a cryptographic key is associated with an entity, the verification operation comprising:
 (a) receiving, over a network:   (a1) period data for a period of time, for computing a first target in computer-implemented computation, wherein the period of time is one of a plurality of periods of time each of which is associated with period data, and the first target is computable, in computer-implemented computation, from the period data associated with any one of the periods of time;   wherein for each set in at least the first plurality, the period data form at least part of a hash tree, each period of time corresponding to the hash tree's node comprising the period data for the period of time, different periods of time corresponding to different nodes, wherein for at least two of the periods of time, one of the corresponding nodes is neither a child nor a parent of the other one of the corresponding nodes;   (a2) first target computation data comprising values of one or more of the nodes for computing, in computer-implemented computation, the first target recited in (a1) from the period data received in (a1);   (a3) second target computation data for computing, in computer-implemented computation, a second target from the first target, wherein the second target is a function of a plurality of first targets each of which is associated with a set comprising the first digital certificate;   (b) computing, in computer-implemented computation, the first target recited in (a1) from the period data and the first target computation data;   (c) computing, in computer-implemented computation, the second target from the first target computed in (b) and from the target computation data;   (d) matching the second target against a value obtained from the first digital certificate to determine the first digital certificate's validity or invalidity.   
     
     
         10 . The network transmission method of  claim 9  wherein for at least one set in the first plurality, for the nodes corresponding to at least two of the periods of time, one of the nodes is a parent of the other one of the nodes in the corresponding hash tree.