Search

A dynamic universal accumulator is an accumulator that allows one to efficiently compute both membership and nonmembership witnesses in a dynamic way. It was first defined and instantiated by Li et al., based on the Strong RSA problem, building on the dynamic accumulator of Camenisch and Lysyanskaya. We revisit their construction and show that it does not provide efficient witness computation in certain cases and, thus, is only achieving the status of a partially dynamic universal accumulator. In particular, their scheme is not equipped with an efficient mechanism to produce non-membership witnesses for a new element, whether a newly deleted element or an element which occurs for the first time. We construct the first fully dynamic universal accumulator based on the Strong RSA assumption, building upon the construction of Li et al., by providing a new proof structure for the non-membership witnesses. In a fully dynamic universal accumulator, we require that not only one can always create a membership witness without having to use the accumulated set for a newly added element, but also one can always create non-membership witnesses for a new element, whether a newly deleted element or an element which occurs for the first time, i.e., a newcomer who is not a member, without using the accumulated set.

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 bit length 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.