Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
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.
