RSA Accumulators with auxiliary information or known trapdoor information

Question

In "Universal Accumulators with Efficient Nonmembership Proofs" by Jiangtao Li1, Ninghui Li2, and Rui Xue3 section "How to compute witness with the auxiliary information" the authors write:

"The membership witness and nonmembership witness can be computed efficiently given the auxiliary information $aux_f$. Suppose there is a trusted group manager who knows $aux_f$, maintains the set $X$, and has already computed the accumulator $c = f(g, X)$, the group manager can compute (non)membership witness for any $x \in X_k$ with one short modular exponentiation.

For $x \in X$, the group manager first checks whether $x \in X$, then computes $a = x^{−1} \bmod \phi(n)$, and finally computes $c_x = c^{a} \bmod n$. The membership witness for $x$ is $c_x$. It is easy to verify the correctness of the witness as $(c_x)^x = (c^a)^x = c^{x^{−1}·x \bmod \phi(n)} = c \bmod n$."

When I try to apply this I always get membership in the accumulator as true, even when the tested number is not in the accumulator.

Example:

$$ c = g^{x_1 x_2 \cdots x_k} \bmod n $$

According to the authors I should calculate the witness of $p$ (a prime number) as:

$$ c_p=c^{p^{−1}mod \phi(n)} \bmod n $$

Then check if $(c_p)^{p} = c$. This is always true if $p^{-1}$ exists. As per the proof presented by the authors, even when $p \notin X$.

On the other hand if I store the full exponent of accumulator $c$ as $e = \prod_{i=1}^k x_i $ I can test if an element is a member of the accumulator or not by calculating:

$$ w_p = g^{e / p \mod \phi(n)} \bmod n $$ $$ c' = (w_p)^p \mod n $$

$$ isMember(p) = \left \{ \begin{aligned} &\text{true}, && \text{if}\ c'=c \\ &\text{false}, && \text{otherwise} \end{aligned} \right. $$

This works but I have to store the full exponent $e$ instead of just storing accumulator $c$ and using trapdoor $\phi(n)$ to calculate witnesses on the fly.

What am I doing wrong? How can I use the knowledge of the accumulator's trapdoor to calculate valid membership, or non-membership, on the fly just by knowing the accumulator's value $c$?

Answer 1

For the inclusion proof you might need the trapdoor or the accumulated set. The exclusion proof can be generated without knowing the trapdoor. See this related question and answer.

How can one generate inclusion proofs if knew the trapdoor, i.e. the factorization of $N=p\cdot q$?

Let's $A$ denote the accumulator's value, $x$ be an item to-be-accumulated and $N$ the modulus whose factorization is known.

Generating a valid membership proof for an item $x$ essentially means taking $x$-th root of $A$ $\mod N$. Since you know the factors of $N$ you can just compute $x$-th root $\mod p$ and then $\mod q$ and afterwards compute the $x$-th root $\mod N$ by applying the Chinese-remainder theorem for moduli $p,q$.

Note, that computing efficiently arbitrary roots mod a prime is simple. See, for instance, here.