I am currently learning about RSA accumulators and this was just a question I had since in most available implementations I see in Github accumulated primes are stored in hash tables and they are required when changing the accumulator state.

I don't understand what makes accumulators useful if you still need to store ALL the accumulated values in order to generate a set membership proof, since there are other public key schemes that allow me to generate set membership proofs the simplest one being using ElGamal cryptosystem along with a Zero Knowledge Proof of Set Membership.

A typical accumulator state looks like this:

$N = p \cdot q$ (p and q are discarded)

$A_{0} = random(bits)$

$c = A_{0}\,^{\prod(members)} mod\, N$ (members are added one by one)

In non-modular arithmethic I could just store the multiplication of all the members then give member a $a0^{mult/a}$ as a proof/witness but I am not sure if something like that would be possible in modular arithmethic (specially without knowing the exponent nor the factorization of $N$).

Is there any way to generate membership proofs (membership or non-membership) just with those parameters without needing to store a ever-growing dataset of the members of the accumulated sets? If the answe is no then what is the use case that cryptogaphic accumulators cover? wouldn't it be the same as other zero knowledge proof of set membership?


Your Answer

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

Browse other questions tagged or ask your own question.