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.

  • $\begingroup$ 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) $\endgroup$
    – 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).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.