# Fake non-membership proof in RSA accumulator

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$$?

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.

• 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?) Nov 27, 2021 at 15:02