RSA accumulator exclusion proof without set

Question

In researching about RSA accumulators I came across this question, Inclusion and Exclusion proofs in RSA accumulators - from the first answer I had assumed that proof of non-membership could be computed without knowledge of the set, i.e. using only the accumulator value itself ($A$), and the element ($x$) not contained in $A$. This is accomplished with Bézout's coefficients $ax+bu=\gcd(x,u)=1$, the proof is $\pi=(𝑔^{𝑎},𝑏)$, verification is checking $(g^{a})^𝑥⋅𝐴^{𝑏}=g^{ax+bu}=𝑔$. If adding a member then proof of membership can be done without the set also.

When I revisited this after looking at a few implementations I realized the implications, 𝑢 is the product of the accumulated elements, and therefore although the individual set members are not required, this product is, and it could potentially be a huge number with many accumulated elements, and therefore storage or communication of 𝑢 might be infeasible quite quickly, as compared to the accumulator itself which uses modular exponentiation.

Have I missed something? Is the exclusion proof possible without the set? I ask as I experimented with say 1,000,000 set members, each with a hash to prime computed for it, e.g. Blake256, and quickly realized that not only is 𝑢 hard to store and communicate with an increasing number of elements but it would take forever to calculate the product of those primes, so in effect, proof of non-membership without knowing the set is only possible with a small number of accumulated elements (providing this product can be communicated and stored)?

If the above is the case, then is there another tool, accumulator, or otherwise, where an exclusion proof is possible without possessing the set members (or the product), or is this fundamentally not possible?

Answer 1

Great observation! Just a quick recap: $A=g^u\bmod{N},$ where $A$ is the accumulated value, $u=\Pi_{i\in S} x_i$, is the product of the accumulated values $x_i$, where $x_i\in S$ and all accumulated values $x_i$ are primes. An exclusion proof of $x$ is a pair of group elements, $\pi=(g^a,b)$ such that $ax+bu=1$, using the Extended Euclidean algorithm, since $x\notin S\implies (x,u)=1$.

There are essentially two possibilities with respect to generating the exclusion proofs in an RSA accumulator.

1. The factorization of $N$ is known

This might occur in some use cases if there is an authority who manages the accumulator, e.g., in the Accumulator Manager setting, see this work for an example. In this case $u\bmod{\phi(N)}$ is computable since $\phi(N)=(p-1)(q-1)$ is computable from the factorization of $N=pq$. You can imagine that the Accumulator Manager periodically updates/publishes $u\bmod{\phi(N)}$ to facilitate to efficient exclusion/inclusion proof generation for its users. Therefore, in this centralized setting the mentioned problem does not occur as the bit length of $\log_2(u)\approx\log_2(\phi(N))\approx\log_2(N)$.

Note that even though the exponent $u$ might be large, the Accumulator Manager can convince its users that given $N,g$ and $u$ the exponentiation $g^u\bmod{N}$ was computed correctly without disclosing its users the factorization of $N$. Efficient proofs of exponentiation protocols were proposed by Pietrzak and Wesolowski.

2. The factorization of $N$ is unknown

This is the tricky setting! Let's assume that there are $n$ accumulated elements, i.e., $\vert S\vert=n$. Then, the size of $u$ is $\log_2(u)=\sum_{x_{i}\in S} \log_2(x_i)=\log_2(p_n\#)$, where $p_n\#$ is the $n$-th primorial. Just to illustrate the growth rate of primorials, $\log_2(p_{2021}\#)=25151$, that is roughly $3.07$ KiB. Unfortunately, $u$ cannot be reduced $\bmod{\phi(N)}$ since the factorization of $N$ is not known. You were not missing anything, if we were in this setting, then unfortunately the RSA accumulator is not efficient to store thousands of elements.

Are there any accumulators that do not require the knowledge of the full set for computing exclusion proofs ?

The simplest example could be a sorted Merkle-tree used as an accumulator. In a sorted Merkle-tree leaves are sorted according to some ordering. In the case of sorted Merkle-trees, computing the exclusion proofs do not increase linearly in the size of the accumulated set, rather logarithmically. With 2 inclusion proofs of neighbouring leaves, a prover can show that a certain leaf between those elements is not contained in the sorted Merkle-tree.