As explained in this answer, if one knows the trapdoor (factorization of modulus $N$) in an RSA accumulator, one can generate fake membership proofs. Does the same apply to non-membership proofs? More specifically:

Given $A$ is the value of an RSA accumulator and $x$ is a value present in $A$, if I know $p$ and $q$, where $N = p \cdot q$, could I generate a non-membership proof saying that $x$ is not in $A$?


1 Answer 1


Yes. More generally, suppose you know the size of the group $\mathbb{G}$ you are working in (RSA, class group etc).

Let $A = g^n$ where $n$ is the product of the elements in the committed set. Assuming $n$ is co-prime to $|\mathbb{G}|$, you can compute integers $a_1$, $a_2$ such that $$a_1 x + a_2 n \equiv 1 \pmod{|\mathbb{G}|}\;\;,\;\; |a_2| < |x|.$$ Setting $w:= g^{a_1}$ yields $w^{x}A^{a_2} = g$ and hence, the pair $(w, a_2) \in \mathbb{G} \times \mathbb{Z}$ works as a fake non-membership proof.

This is a fake non-membership proof for a single element. But with a little more work, you can also create a fake constant-sized proof for an arbitrarily large subset as in the BBF19 paper (https://eprint.iacr.org/2018/1188). The PoKE protocol in the paper (which is necessary for non-membership proofs) depends on the strong-RSA and adaptive root assumptions, both of which assume the group order is unknown.

  • $\begingroup$ Isn't that only possible if (x, n) are co-primes. (Bezout's identity) that means a2 can't be a divisor of n, So it's not fake. What am I missing? Why is there a mod |G| (We aren't doing any mod in the verification, right?) $\endgroup$ Commented Nov 27, 2021 at 15:02

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.