Dynamic accumulator with only non-membership witness

Question

Goal: Construct a dynamic accumulator which can add elements and provide non-membership witnesses. I wanted to know if my construction is correct.

Consider a group $Z_p$ where $p$ is prime number. Consider the set $S=\{c_1, c_2,\cdots, c_m\}$ where $c_i\in Primes(Z_p)$. Consider the following accumulator: $$ A = \left(\prod_{c_i \in S} c_i\right) \text{mod } p. $$

Addition: To add a new element $c \in Primes(Z_p)$, $$ A \longleftarrow \left(A\times c\right) \text{mod } p. $$

Non-Memerbship witness $(x,y)$: To show $c \not\in S$, we use the fact that $c$ is co-prime with all the elements in $S$. We use Bezout coefficient $(x,y)$ to show that $$ cx+Ay=1 \text{ mod } p. $$

Security: $\forall c\in S$, there exists no algorithm $\mathcal{A}$ such that

$$ (x,y) \leftarrow \mathcal{A}(c,S),\; cx+Ay=1 \text{ mod } p. $$

Answer 1

This is not a correct dynamic accumulator scheme.

Your scheme assumes that the following holds: if $a,b$ are primes and $0< a,b < p$, then $$(a,b)=1 \implies (ab\mod p,a)\neq1. $$ If this is true, then your scheme is correct, however this is not the case.

Toy example: $p=11,a=5,b=7$. Since $ab \mod 11=35 \mod 11=2,$ therefore $A=2$. Now, it is clear that security does not hold, since one could prove false non-membership statements. The reason for that is: $(a,A)=1=(b,A)$. Meaning one can prove that $a$ and $b$ are not accumulated however they were indeed added to the accumulator. For instance $(2,1)$ is a a non-membership witness for $5$, when $A=2$, since $5*2+2*1 \mod 11 = 1$.