Discrete log accumulator without pairings?

Question

Here $g$ is some fixed generator of a discrete log group. I don't want the group to be bilinear for efficiency and BDH-skepticism reasons.

Is anyone aware of a discrete log accumulator? What I mean specifically is some function $f(x, A)\mapsto A'$ (that is, $A$ is the accumulator value; $f$ adds $x$ to the accumulator, changing its value to $A'$) such that given $(g^x, A')$ anyone can check whether $x$ was placed in the accumulator.

So I'm roughly asking for an accumulator with the property that an accumulated element $x$ has $g^x$ as a witness.

Answer 1

Sure. Use the strong RSA assumption. The accumulator of $x_1,\dots,x_k$ is $A = g^{x_1 x_2 \cdots x_k} \bmod n$, where $n$ is a RSA modulus and $g$ is a fixed base. To prove that the accumulator $A$ contains $x$, exhibit a value $h$ such that $h^x=A \pmod n$. This is secure under the strong RSA assumption, and has a discrete log "feel" to it.

Answer 2

Looks like one of the vector commitment (VC) schemes by Catalano and Fiore comes closest to what you need [1]. Specifically, the one based on Computational Diffie Hellman (CDH) (see Section 3.1 in their paper).

You might also be able to verify membership of $x$ using $g^x$ rather than $x$ itself if you can use a discrete log equality proof between the VC's ${h_i}^x$ used during verification in $\mathsf{VC.Ver}$ and your $g^x$.

Later edit: I did not include the accumulator based on Strong RSA since you only mentioned discrete log as an assumption. If you're okay with Strong RSA, there is a way to check that a committed element is in the accumulator (see "Dynamic accumulators and application to efficient revocation of anonymous credentials", by Camenisch & Lysyanskaya).