Method and apparatus for providing efficient management of certificate revocation

US 9 083 535B2

drawing #0

Show all 8 drawings

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.

PatentSwarm provides a collaborative workspace to search, highlight, annotate, and monitor patent data.

Start free trial Sign in

Tip: Select text to highlight, annotate, search, or share the selection.

Claims

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.

Show 5 dependent claims

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.

Show 5 dependent claims

Description

This application was originally filed as PCT Application No. PCT/IB2010/055047 filed Nov. 5, 2010

TECHNOLOGICAL FIELD

An embodiment of the present invention relates generally to public key cryptography and, more particularly, relates to a method and apparatus for providing efficient management of certificate revocation.

BACKGROUND

The modern communications era has brought about a tremendous expansion of wireline and wireless networks. Computer networks, television networks, and telephony networks are experiencing an unprecedented technological expansion, fueled by consumer demand. Networking technologies have addressed related consumer demands, while providing more flexibility and immediacy of information transfer.

Current and future networking technologies continue to facilitate ease of information transfer and convenience to users by expanding the capabilities of electronic devices and by improving network performance. One advance that has improved the capabilities of electronic devices to provide services to users is the use of public key cryptography. Public key cryptography uses people, equipment and policies to manage the generation, use and revocation of digital certificates. A certificate authority (CA) is typically responsible for issuing the digital certificates.

Public key cryptography assumes the existence of a pair of keys for each user, a private key and a public key. The keys are bound to each other in a way that protects the system from malicious users. The validity of these keys and the fact that a key belongs to an identity is assured by the CA through publishing of the digital certificate. Once the identities and their keys are in place, users can employ their respective certificates to identify themselves to each other. Certificates typically have a natural expiration date, but they can be revoked before they expire naturally as well.

Networks use information indicative of the identity of devices for both enabling authorized devices to use the network and for preventing other devices from having access privileges based on the status of the certificates. When a device has access to a guaranteed broadband channel, the device can contact the appropriate authority to confirm identification of a certain user. However, a problem may arise when a device does not have any reliable access to a server, or the access is of low bandwidth, both of which may make the process of identification much more complex.

Situations where guaranteed access to a base station is not available can arise under any of a number of circumstances. For example, being in remote areas or being in tunnels or other underground or heavily shielded environments are not uncommon situations for some people to encounter. As such, a user may have a device that does not have guaranteed access to a user that is trusted, while other devices that are more powerful or otherwise situated advantageously may still be able to access a local server. Accordingly, it is typically important for users to be able to identify other devices that they encounter since some could be malicious and intrusive.

BRIEF SUMMARY

A method, apparatus and computer program product are therefore provided to enable efficient management of certificate revocation. In this regard, for example, some embodiments may use an accumulator that is useful for batch updates, allows employment of semi-trusted delegates and may employ zero-knowledge techniques to make proof of non-revocation non-transferable. Some example embodiments may also or alternatively provide for the use of a counter Bloom filter to provide efficient compression without requiring recomputing of the entire Bloom filter for each modification made thereto.

In one example embodiment, a method of providing efficient management of certificate revocation is provided. The method 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 the 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.

In another example embodiment, an apparatus for providing efficient management of certificate revocation is provided. The apparatus may comprise at least one processor and at least one memory including computer program code. The at least one memory and the computer program code may be configured to, with the at least one processor, cause the apparatus to perform at least 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 the 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.

In one example embodiment, another apparatus for providing efficient management of certificate revocation is provided. The apparatus may comprise means for storing a list of identifiers of digital certificates including a revocation list defining a list of revoked certificates in an accumulator, means for 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, means for 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 means for enabling batch updates to the revocation list using a reduced bitlength value generated based on the 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.

In one example embodiment, a method for providing efficient management of certificate revocation is provided. The method may comprise causing compression of a certificate revocation list using a counter filter at a certificate authority in which the counter filter comprises a plurality of counter positions and each of the counter positions corresponds to a hash function of a revoked certificate identifier, causing conversion of values in the counter filter to binary values such that values greater than zero are converted to ones to form a binary filter, and causing transmission of the binary filter to provide the certificate revocation list to another entity.

In another example embodiment, an apparatus for providing efficient management of certificate revocation is provided. The apparatus may comprise at least one processor and at least one memory including computer program code. The at least one memory and the computer program code may be configured to, with the at least one processor, cause the apparatus to perform at least causing compression of a certificate revocation list using a counter filter at a certificate authority in which the counter filter comprises a plurality of counter positions and each of the counter positions corresponds to a hash function of a revoked certificate identifier, causing conversion of values in the counter filter to binary values such that values greater than zero are converted to ones to form a binary filter, and causing transmission of the binary filter to provide the certificate revocation list to another entity.

In one example embodiment, another apparatus for providing efficient management of certificate revocation is provided. The apparatus may comprise means for causing compression of a certificate revocation list using a counter filter at a certificate authority in which the counter filter comprises a plurality of counter positions and each of the counter positions corresponds to a hash function of a revoked certificate identifier, means for causing conversion of values in the counter filter to binary values such that values greater than zero are converted to ones to form a binary filter, and means for causing transmission of the binary filter to provide the certificate revocation list to another entity.

BRIEF DESCRIPTION OF THE DRAWING(S)

Having thus described some embodiments of the invention in general terms, reference will now be made to the accompanying drawings, which are not necessarily drawn to scale, and wherein:

FIG. 1 is a schematic block diagram of a wireless communications system according to an example embodiment of the present invention;

FIG. 2 illustrates a block diagram of an apparatus for providing efficient management of certificate revocation according to an example embodiment of the present invention;

FIG. 3 illustrates a binary Bloom filter according to an example embodiment;

FIG. 4 illustrates a counter Bloom filter according to one example embodiment of the present invention;

FIG. 5 illustrates an example of a counter Bloom filter generated at a certificate authority and an example of a corresponding binary Bloom filter generated based on the counter Bloom filter and communicated to the according to an example embodiment of the present invention;

FIG. 6 is a flowchart according to an example method for providing efficient management of certificate revocation according to an example embodiment of the present invention; and

FIG. 7 is a flowchart according to another example method for providing efficient management of certificate revocation according to an example embodiment of the present invention.

DETAILED DESCRIPTION

Some embodiments of the present invention will now be described more fully hereinafter with reference to the accompanying drawings, in which some, but not all embodiments of the invention are shown. Indeed, various embodiments of the invention may be embodied in many different forms and should not be construed as limited to the embodiments set forth herein; rather, these embodiments are provided so that this disclosure will satisfy applicable legal requirements. Like reference numerals refer to like elements throughout. As used herein, the terms data, content, information and similar terms may be used interchangeably to refer to data capable of being transmitted, received and/or stored in accordance with some embodiments of the present invention. Thus, use of any such terms should not be taken to limit the spirit and scope of embodiments of the present invention.

Additionally, as used herein, the term circuitry refers to (a) hardware-only circuit implementations (e.g., implementations in analog circuitry and/or digital circuitry); (b) combinations of circuits and computer program product(s) comprising software and/or firmware instructions stored on one or more computer readable memories that work together to cause an apparatus to perform one or more functions described herein; and (c) circuits, such as, for example, a microprocessor(s) or a portion of a microprocessor(s), that require software or firmware for operation even if the software or firmware is not physically present. This definition of circuitry applies to all uses of this term herein, including in any claims. As a further example, as used herein, the term circuitry also comprises an implementation comprising one or more processors and/or portion(s) thereof and accompanying software and/or firmware. As another example, the term circuitry as used herein also comprises, for example, a baseband integrated circuit or applications processor integrated circuit for a mobile phone or a similar integrated circuit in a server, a cellular network device, other network device, and/or other computing device.

As defined herein a computer-readable storage medium, which refers to a non-transitory, physical storage medium (e.g., volatile or non-volatile memory device), can be differentiated from a computer-readable transmission medium, which refers to an electromagnetic signal.

As indicated above, some embodiments of the present invention may relate to the management of digital certificate revocations. In an example situation, a certificate authority (CA) may handle certification and revocation processes for various mobile devices. A first mobile device and a second mobile device may be positioned such that both the first and second mobile devices do not have guaranteed access to a network. Accordingly, it may be desirable for provision of a mechanism by which, for example, the first mobile device may authenticate itself to the second mobile device by providing a valid, non-revoked certificate when both the first and second mobile devices are offline.

One way to accomplish the authentication described above may be for the CA to create a compressed certificate revocation list (CRL) that may be sent to users over relatively low bandwidth channels. The users may receive the CRL over the low bandwidth channel and perform offline verification of other users based on the contents of the CRL. Some embodiments of the present invention may provide for the use of an accumulator of certificate identifiers and also provide techniques for proving membership (or non-membership) of entries in the accumulator. Some embodiments may also provide the potential for distribution of the techniques described herein over one or more delegated authorities (or nodes), that can be fully trusted nodes when such delegation is undertaken.

In some embodiments, Bloom filters may be used for CRL compression. An example Bloom filter is shown in FIG. 3. Bloom filters typically comprise an m-bit vector with all bits initially set to zero. An element can be comprised in the filter by (1) hashing the element with k independent hash functions that output numbers in the range 1, . . . , m, or (2) setting the vector bit to which each hash function points to one. It is possible that one bit may be set to one multiple times due to the addition of several elements. The Bloom filter may then be distributed or published as a compressed list of elements. To check that a given element is contained in the filter, the element may be hashed and the corresponding filter bits may be checked. If at least one of the bits is zero, then the element is not included in the filter. Otherwise, if all necessary k bits are set, typically the element has a high probability of being included. The corresponding bits may have been set also due to multiple additions of other elements (false positive). The more elements added, the higher the probability of encountering false positives.

Bloom filters may be used in connection with databases, in peer-to-peer applications and other communication related environments. Bloom filters may offer high compression rates with relatively low false positives and no false negatives. Accordingly, due to the relatively good compression that can be offered by Bloom filters, the use of Bloom filters for providing CRL compression to adapt CRL provision to low bandwidth channels may be advantageous. However, Bloom filters are sometimes considered to be computationally complex and may require computation of the whole list again after un-revoking a certificate at the CA. Some example embodiments of the present invention have therefore been designed to support un-revoking with relatively light computations on only the certificate that is to be un-revoked. Thus, the compression advantages of Bloom filters may be maintained, while avoiding the necessary resource consumption associated with computation of the whole list again.

Many past solutions have assumed the existence of trusted infrastructures or parties, or have employed techniques that are computationally complex and/or require large amounts of communication bandwidth. As indicated above, some example embodiments may provide for the use of accumulators and/or Bloom filters for use in CRL compression to allow CRL usage in low bandwidth environments.

FIG. 1 illustrates a generic system diagram in which a device such as a mobile terminal 10, which may benefit from some embodiments of the present invention, is shown in an example communication environment. As shown in FIG. 1, a system in accordance with an example embodiment of the present invention comprises a first communication device (e.g., mobile terminal 10) and a second communication device 20 that may each be capable of communication with a network 30. The second communication device 20 is provided as an example to illustrate potential multiplicity with respect to instances of other devices that may be included in the network 30 and that may practice an example embodiment. The communications devices of the system may be able to communicate with network devices or with each other via the network 30. In some cases, the network devices with which the communication devices of the system communicate may comprise a service platform 40. In an example embodiment, the mobile terminal 10 (and/or the second communication device 20) is enabled to communicate with the service platform 40 to provide, request and/or receive information. In some examples, the service platform 40 (or another portion of the network 30) may host a certificate authority (CA) as described in greater detail below.

While an example embodiment of the mobile terminal 10 may be illustrated and hereinafter described for purposes of example, numerous types of mobile terminals, such as portable digital assistants (PDAs), pagers, mobile televisions, mobile telephones, gaming devices, laptop computers, cameras, camera phones, video recorders, audio/video player, radio, global positioning system (GPS) devices, navigation devices, or any combination of the aforementioned, and other types of multimedia, voice and text communications systems, may readily employ an example embodiment of the present invention. Furthermore, devices that are not mobile may also readily employ an example embodiment of the present invention. As such, for example, the second communication device 20 may represent an example of a fixed electronic device that may employ an example embodiment. For example, the second communication device 20 may be a personal computer (PC) or other terminal.

In some embodiments, not all systems that employ embodiments of the present invention may comprise all the devices illustrated and/or described herein. For example, while an example embodiment will be described herein in which either a mobile user device (e.g., mobile terminal 10), a fixed user device (e.g., second communication device 20), or a network device (e.g., the service platform 40) may comprise an apparatus capable of performing some example embodiments in connection with communication with the network 30, it should be appreciated that some embodiments may exclude one or multiple ones of the devices or the network 30 altogether and simply be practiced on a single device.

In an example embodiment, the network 30 comprises a collection of various different nodes, devices or functions that are capable of communication with each other via corresponding wired and/or wireless interfaces. As such, the illustration of FIG. 1 should be understood to be an example of a broad view of certain elements of the system and not an all inclusive or detailed view of the system or the network 30. Although not necessary, in some embodiments, the network 30 may be capable of supporting communication in accordance with any one or more of a number of first-generation (1G), second-generation (2G), 2.5G, third-generation (3G), 3.5G, 3.9G, fourth-generation (4G) mobile communication protocols, Long Term Evolution (LTE), and/or the like.

One or more communication terminals such as the mobile terminal 10 and the second communication device 20 may be capable of communication with each other via the network 30 and each may comprise an antenna or antennas for transmitting signals to and for receiving signals from a base site, which could be, for example a base station that is a part of one or more cellular or mobile networks or an access point that may be coupled to a data network, such as a local area network (LAN), a metropolitan area network (MAN), and/or a wide area network (WAN), such as the Internet. In turn, other devices such as processing devices or elements (e.g., personal computers, server computers or the like) may be coupled to the mobile terminal 10 and the second communication device 20 via the network 30. By directly or indirectly connecting the mobile terminal 10, the second communication device 20 and other devices to the network 30, the mobile terminal 10 and the second communication device 20 may be enabled to communicate with the other devices (or each other), for example, according to numerous communication protocols including Hypertext Transfer Protocol (HTTP) and/or the like, to thereby carry out various communication or other functions of the mobile terminal 10 and the second communication device 20, respectively.

Furthermore, although not shown in FIG. 1, the mobile terminal 10 and the second communication device 20 may communicate in accordance with, for example, radio frequency (RF), Bluetooth (BT), Infrared (IR) or any of a number of different wireline or wireless communication techniques, including USB, LAN, wireless LAN (WLAN), Worldwide Interoperability for Microwave Access (WiMAX), WiFi, ultra-wide band (UWB), Wibree techniques and/or the like. As such, the mobile terminal 10 and the second communication device 20 may be enabled to communicate with the network 30 and each other by any of numerous different access mechanisms. For example, mobile access mechanisms such as wideband code division multiple access (W-CDMA), CDMA2000, global system for mobile communications (GSM), general packet radio service (GPRS) and/or the like may be supported as well as wireless access mechanisms such as WLAN, WiMAX, and/or the like and fixed access mechanisms such as digital subscriber line (DSL), cable modems, Ethernet and/or the like.

Citations

US 2006 137,006 A1 - Use of modular roots to perform authentication including, but not limited to, authentication of validity of digital certificates
Authentication of elements (e.g. digital certificates 140) as possessing a pre-specified property (e.g. being valid) or not possessing the property is performed by (1) assigning...

US 2008 34,203 A1 - NON-TRANSFERABLE ANONYMOUS CREDENTIAL SYSTEM WITH OPTIMAL ANONYMITY REVOCATION
The present invention relates to a method and system for securely proving ownership of pseudonymous or anonymous electronic credentials. A credential system is described consisting...

US 2005 53,045 A1 - Method and system for distributed certificate management in ad-hoc networks
A method and system for distributed certificate management in an ad-hoc network including a plurality of nodes, the method includes making a certificate revocation list...

US 2005 71,631 A1 - Method and system for authorizing client devices to receive secured data streams
A method and system for authorizing client devices to receive secured data streams through the use of digital certificates embedded in the client devices. A...

PatentSwarm provides a collaborative workspace to search, highlight, annotate, and monitor patent data.

Start free trial Sign in