# Update non-member witness in RSA accumulator

According to study of "Universal Accumulators with Efficient Nonmembership Proofs", I don't understand exactly how to update non-member witness in construction 4.2.

In the addition step, I understood the point until finding $$r$$. I can't understand why new non-member witness $$d' = d \cdot c^r$$.

Can somebody explain how to obtain this result please?

Here is the link: https://www.cs.purdue.edu/homes/ninghui/papers/accumulator_acns07.pdf (Construction 4.2: Update of Nonmembership Witness)

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:

1. 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.
2. 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}.$$