Update non-member witness in RSA accumulator

Question

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)

Answer 1

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