Recall that for a set of elements $X=\{x_1,\cdots,x_n\}\subseteq\mathcal{X}$
- the value of the accumulator is $c=g^u\bmod{N}$, where $u:=\Pi_i x_i$; and
- the witness of non-membership for an element $x\not\in X$ is the pair $(a,d=g^{-b})\in\mathbb{Z}\times\mathbb{Z}_N^*$, where $a$ and $b$ are integers satisfying Bézout's identity $$au+bx=1,\tag{0}$$
which is verified by checking whether $$c^a=d^xg\bmod{N}.\tag{1}$$
We are considering the case where an element $\hat{x}\neq x\in\mathcal{X}$ has been added to $X$, i.e., the new set is $\hat{X}:=X\cup\{\hat{x}\}$, and this has resulted in the accumulator value
$$\hat{c}:=g^{\hat{u}}=(g^u)^{\hat{x}}=c^\hat{x}\bmod{N},$$
where $\hat{u}:=u\cdot \hat{x}$. We would like to update the witness of non-membership for $x$ to $(\hat{a},\hat{d}=g^{-\hat{b}})$, where $\hat{a}$ and $\hat{b}$ are integers satisfying Bézout identity
$$\hat{a}\hat{u}+\hat{b}x=1.\tag{2}$$
This could be done from scratch, but it is desirable to derive it efficiently from the previous witness $(a,d)$ and accumulator value $c$. I did not quite understand how it is done in the paper, but another way to accomplish the same would be as follows:
- Find integers $\hat{a}_0$ and $r_0$ satisfying Bézout's identity
$$
\hat{a}_0\hat{x}+r_0x=1.\tag{3}
$$
Note that this is possible since $x$ and $\hat{x}$ are co-primes.
- Set $\hat{a}=\hat{a}_0a$ and $\hat{d}=dc^r\bmod{N}$, where $r=r_0a\in\mathbb{Z}$ .
Let's see why Step 2 works. Our goal is to go from (3) to (2) and we do this using (0): let's multiply $(3)$ on the left by $au$ and on the right by $1-bx$ yielding
$$\begin{align}
\hat{a}_0\hat{x}(au)+r_0x(au)=1(1-bx)
&\Leftrightarrow \hat{a}_0a(\hat{x}u)+(r_0au+b)x=1\\
&\Leftrightarrow (\hat{a}_0a)\hat{u}+(r_0au+b)x=1\\
&\Leftrightarrow \hat{a}\hat{u}+\hat{b}x=1,
\end{align}
$$
where we set $\hat{a}=\hat{a}_0a$ and $\hat{b}=r_0au+b$. Now, observe that although we can compute $\hat{a}$ we cannot compute $\hat{b}$ (since we don't know $u$). However, what we need is $g^{-\hat{b}}$ and it is possible to compute this from $c$ and $d$ as
$$g^{-\hat{b}}=g^{-r_0au-b}=(g^u)^{-r_0a}g^{-b}=c^{-r_0a}d\bmod{N}.$$