# Dynamic accumulator with only non-membership witness

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

• See the Construction 2 of lilixue paper for nonmembership-witness – Narodism Jul 14 '19 at 20:33
• @Narodism Welcome to crypto.stackexchange - It would help improve the quality and reception of your answer if you could link to the relevant paper and summarize the relevant portion of it here – Ella Rose Jul 14 '19 at 23:02
• @Narodism I have converted your answer to a comment for now as it seems more like a reference suggestion than a proper answer. Please use Ella's advice to write a new answer once you have the summary. – SEJPM Jul 15 '19 at 13:05

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