Dynamic universal accumulators for DDH groups and their application to attribute-based anonymous credential systems

We present the first dynamic universal accumulator that allows (1) the accumulation of elements in a DDH-hard group G and (2) one who knows x such that y = gx has - or has not - been accumulated, where g generates G, to efficiently prove her knowledge of such x in zero knowledge, and hence without revealing, e.g., x or y. We introduce the Attribute-Based Anonymous Credential System, which allows the verifier to authenticate anonymous users according to any access control policy expressible as a formula of possibly negated boolean user attributes. We construct the system from our accumulator.