A Fully Dynamic Universal Accumulator

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.