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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.