# Discrete log accumulator without pairings?

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.

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.
• According to the original paper by Benaloh and de Mare, the RSA modulus in this case should be chosen s.t. the order of $g$ has no small prime factors (and $g$ doesn't have to generate the complete multiplicative group). One stated example is both $p$ and $q$ being safe primes and $g$ having order $(p-1)/2 \cdot (q-1)/2$ (which is a product of two large primes) – tylo Dec 12 '17 at 13:55
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$.