I read this paper on RSA cryptographic accumulators have some questions on a few points :

"Universal Accumulators with Efficient Nonmembership Proofs" https://www.cs.purdue.edu/homes/ninghui/papers/accumulator_acns07.pdf

I noticed this from the paper :

"Note that computing witness using auxiliary information may not apply to all scenarios. In some applications, it is not allowed to reveal the auxiliary information to the party who computes the accumulator, since the auxiliary data enables her to prove arbitrary statements. In the case when the party who computes the accumulator is trusted, it is acceptable to give her the auxiliary information."

If an untrusted party gets the p and q that make the modulus, what does it mean that mean they can prove arbitrary statements? Does it mean that they can prove something like : any number x is both a member and a non member of the accumulator?

Also, for parties that don’t have the p and q, then deletion is not efficient correct? I am under the impression that p and q's properties, and using them for the deletion is what adds the efficiency in this paper.

If you have an accumulator that you haven't put x into, and you delete x from the accumulator even though x wasn’t in it in the first place to remove [you can do it because you have aux: p and q] Does that let you produce a witness that you can use to prove x is a member of the accumulator? (Witness)**x = Original Accumulator ? Even though x was never in the accumulator to start with? Or will it result in an “invalid” witness, because x was never in there?

I also noticed from the paper :

"In other words, it is computationally infeasible to find both a valid membership witness and a valid nonmembership witness for any x in Xk. Note that this is equivalent to say that, given any set X ∈ Xk, it is computationally infeasible to find x ∈ X with a valid nonmembership witness or find x ∈ Xk\X with a valid membership witness." Is this only computationally infeasible if you don’t know the primes p and q which make n?

I was hoping that even if you knew p and q, that it would be computationally infeasible to find both membership and non membership witnesses that satisfy, but accumulators may not have that property. i.e. like it says, can prove arbitrary statements with p and q.

My use case, is that I wanted two parties to have access to p and q, and generator g. One party maintains the accumulator and updates it. They send the accumulator to the second party. The second party uses it to check the set membership of an element x They remove x from the accumulator using subtraction It creates an “invalid witness” that is either not in the group the witness and x together don’t bilinear map to the original accumulator. I was hopeful that I could detect if x was in an accumulator just from the inputs (Accumulator, x, g, p, q) without the original set, but I am not sure if that is possible.

It would be great because it would involve only passing around the RSA accumulator which is very small.

Is there a way of doing this? Thanks!


1 Answer 1


As a general rule of thumb: In RSA, everyone with the factorization p and q can do everything, except calculating dlogs. If you spread that knowledge over multiple parties, you can skip RSA entirely: There us no meaningful security to achieve at all - unless you depend on the DLOG problem, and then better use a finite field directly. With knowledge of the factorization, typical RSA trapdoor functions don't work anymore.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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