# RSA Accumulators with auxiliary information or known trapdoor information

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$$?

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.

• Thank you for the suggestion. I'm trying to validate membership in the accumulator, and since secrecy is not a requirement all parameters N, p, q, and accumulator value are known. What is not known are the actual elements ($x_1, x_2, \cdots, x_n$) that built the accumulator. How can I test if a prime number $y$ has been accumulated? – Pedro Paixao Dec 7 '19 at 5:39
• By using the Chinese-remainder theorem with each of the x-th roots of A mod p and mod q, I get the same witness as calculating $w_x=A^{x^{-1}} \bmod N$ directly which is what we expect, and then when I test for membership by checking $w_x^{x} == A$ I always get this to be true even when $x$ had not been accumulated. How can I test if a given value has been accumulated or not if the person doing the verification does not know the members of the set that generated the accumulator? – Pedro Paixao Dec 7 '19 at 6:05
• You can only take $x$th roots of the accumulator value $A$ if $x$ was indeed accumulated. Otherwise you will not find such an $x$th root, namely you will not find a solution to the equation $w_x=A^{x^{-1}}$ . – István András Seres Dec 7 '19 at 9:51
• I think your misunderstanding stems from the implicit assumption of yours, that the $a\rightarrow a^x$ function in $\mathbb{F}_p$ is injective. However, this map is far from being injective. – István András Seres Dec 7 '19 at 10:02