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)


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.