Method and apparatus for providing efficient management of certificate revocation

Patent metadata

Field	Value
Publication number	US-9083535-B2
Application number	US-201013882812-A
Country	US
Kind code	B2
Filing date	Nov 5, 2010
Priority date	Nov 5, 2010
Publication date	Jul 14, 2015
Grant date	Jul 14, 2015

Abstract

A method for providing efficient management of certificate revocation may comprise storing a list of identifiers of digital certificates including a revocation list defining a list of revoked certificates in an accumulator, storing a witness value in association with at least some entries in the revocation list in which the witness value provides proof of the membership or non-membership of an identifier in the revocation list, enabling generation of a new accumulator and a new witness value responsive to each insertion or deletion of an entry in the revocation list, and enabling batch updates to the revocation list using a reduced bitlength value generated based on to a ratio of a value generated based on elements added to the revocation list to a value generated based on elements deleted from the revocation list. A corresponding apparatus is also provided. A method for certificate authorities (CA) that use Bloom filters for certificate revocation list (CRL) compression that enables the CA to hash only the entry that is to be un-revoked so that a good compression rate may be provided while avoiding computation of the entire CRL for each un-revocation.

First claim

What is claimed is:

1. A method comprising:
storing a list of identifiers of digital certificates including a revocation list defining a list of revoked certificates in an accumulator;
storing a witness value in association with at least some entries in the revocation list, the witness value providing proof of the membership or non-membership of an identifier in the revocation list;
enabling generation of a new accumulator and a new witness value responsive to each insertion or deletion of an entry in the revocation list; and
enabling batch updates to the revocation list using a reduced bitlength value generated based on to a ratio of a first value generated based on elements added to the revocation list to a second value generated based on elements deleted from the revocation list.

2. The method of claim 1 , wherein enabling batch updates comprises using the reduced bitlength value r replaced by y=r mod λ(n), where r=A/D and where a i defines elements to be added in a row, A=Πa i , and d i defines elements to be deleted in a row, D=Πd i , to add y as an entry to a set X to update witness values and λ(n) is the least common multiplier of (p 1 −1) a−1 1 , . . ., (p v −1) a−1 v , where p i are primes of a unique factorization of n.

3. The method of claim 1 , wherein storing the list, storing the witness value, enabling generation of the new accumulator and the new witness value, and enabling batch updates is performed at a certificate authority.

4. The method of claim 3 , wherein storing the list, storing the witness value, enabling generation of the new accumulator and the new witness value, and enabling batch updates is enabled to be performed at a semi-trusted delegate.

5. The method of claim 4 , wherein the certificate authority is enabled to monitor activity of the semi-trusted delegate with respect to at least generation of the new witness value and revoke the semi-trusted delegate based on irregularities associated with generation of the new witness value.

6. The method of claim 4 , wherein the semi-trusted delegate is enabled to generate witness values to provide proof of membership or non-membership using a zero-knowledge proof mechanism.

7. An apparatus comprising at least one processor and at least one memory including computer program code, the at least one memory and the computer program code configured to, with the at least one processor, cause the apparatus at least to:
store a list of identifiers of digital certificates including a revocation list defining a list of revoked certificates in an accumulator;
store a witness value in association with at least some entries in the revocation list, the witness value providing proof of the membership or non-membership of an identifier in the revocation list;
enable generation of a new accumulator and a new witness value responsive to each insertion or deletion of an entry in the revocation list; and
enable batch updates to the revocation list using a reduced bitlength value generated based on to a ratio of a first value generated based on elements added to the revocation list to a second value generated based on elements deleted from the revocation list.

8. The apparatus of claim 7 , wherein the at least one memory and computer program code are configured to, with the at least one processor, cause the apparatus to enable batch updates by using the reduced bitlength value r replaced by y=r mod λ(n), where r=A/D and where a i defines elements to be added in a row, A=Πa i , and d i defines elements to be deleted in a row, D=Πd i to add y as an entry to a set X to update witness values and λ(n) is the least common multiplier of (p 1 −1) a−1 1 , . . . , (p v −1) a−1 v , where p i are the primes of the unique factorization of n.

9. The apparatus of claim 7 , wherein the apparatus is embodied at a certificate authority.

10. The apparatus of claim 9 , wherein the at least one memory and computer program code are configured to, with the at least one processor, cause the apparatus to store the list, store the witness value, enable generation of the new accumulator and the new witness value, and enable batch updates at a semi-trusted delegate.

11. The apparatus of claim 10 , wherein the certificate authority is enabled to monitor activity of the semi-trusted delegate with respect to at least generation of the new witness value and revoke the semi-trusted delegate based on irregularities associated with generation of the new witness value.

12. The apparatus of claim 10 , wherein the semi-trusted delegate is enabled to generate witness values to provide proof of membership or non-membership using a zero-knowledge proof mechanism.

Assignees

• Mashatan Atefeh
• Aad Imad
• Chaabouni Rafik
• Niemi Pentti Valtteri
• Vaudenay Serge
• Nokia Corp

Inventors

• Mashatan Atefeh
• Aad Imad
• Chaabouni Rafik
• Niemi Pentti Valtteri
• Vaudenay Serge

Classifications

• H04L63/20 Primary

  for managing network security; network security policies in general (filtering policies H04L63/0227) · CPC title

• H04L9/3268 Primary

  using certificate validation, registration, distribution or revocation, e.g. certificate revocation list [CRL] · CPC title

• H04L63/0823

  using certificates (cryptographic mechanisms or cryptographic arrangements for entity authentication involving certificates H04L9/3263) · CPC title

• Y04S40/20

  Information technology specific aspects, e.g. CAD, simulation, modelling, system security · CPC title