# 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.

## 2 Answers

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

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).