My question concerns accumulation of new elements in bilinear (pairing-based) accumulators.

Suppose you have a pairing $e:\mathbb{G}_1\times \mathbb{G}_2 \longrightarrow \mathbb{G}_T$ with generators $g_1, g_2$ for the cyclic groups $\mathbb{G}_1$, $\mathbb{G}_2$. The accumulated state is defined as $$A = g_1^{\prod\limits_{d\in D} (s+d)} $$ where $s$ is the private key (i.e. the trapdoor). What is the most efficient way to add the elements of a new set $D_1$ to the accumulator?

It seems that without the trapdoor, one would need to keep track of the coefficients of the polynomial $\prod\limits_{d\in D} (s+d)$ and keep updating this set of coefficients which grows linearly with the size of the accumulated set.

More generally, given an element $a\in \mathbb{G}_1$ how does one compute $a^s$ without using the polynomial $h(X)$ such that $a =g_1^{h(s)}$?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.