# Multiplication of pairings vs. exponentiation of the group elements

Assume that we have a pairing as $$e:G_1\times G_2\rightarrow G_T$$. such that $$g_1$$ and $$g_2$$ are the generator of $$G_1$$ and $$G_2$$ respectively. In a protocol I have $$A=\prod_{i=1}^n e(H(i),pk_i)$$ where $$H(i)\in G_1$$ and its discrete-logarithm is unknown (since it is a random oracle) and $$pk_i\in G_2$$. I can design another protocol such that I can compute my target value $$A$$ in another way i.e., $$A=e(H(l),\prod_i pk_i^{a_i})$$ (where $$H(l)\in G_1$$ and independent of index $$i$$). The groups $$G_1,G_2,G_3$$ are the same in both schemes.

Thus the point which I am interested in is the efficiency. The main difference in these two evaluations is that:

In the first scheme we have $$n$$ pairing and $$n$$ multiplication over $$G_T$$. While in the second scheme, we have $$n$$ exponentiation over $$G_2$$ (exponents of $$a_i$$), $$n$$ multiplication in $$G_2$$ and 1 pairing.

Which of these schemes is more efficient? could you please give me some link and references for a precise comparison. Is the efficiency gain noticeable?

• Scheme 2 is almost certainly going to be more efficient. This is because an exponentiation in $G_2$ is almost always significantly faster than a pairing, and moreover, in Scheme 2, you can use multi-exponentiation techniques to further greatly speed up the computation of $\prod_i \textit{pk}_i^{a_i}$ compared to naively doing $n$ exponentiations and products. Sep 17 at 16:35
• @MehdiTibouchi: other than providing a reference (which, IMHO, is unneeded, given the size of the performance difference), this appears to fully answer the question. Should you submit it as an answer? Sep 17 at 16:53
• There are the equivalent speed-ups for multi-exponentiation in the evaluation of products of pairings. In Miller's algorithm (left-to-right), a single squaring can be used for the squaring step in each component pairing. The broader point that $n$-exponentiations in $G_2$ is likely to take $(1+n\epsilon)\log\ell$ field multiplications and even the Tate pairing is likely to take at least $(6n+\epsilon)\log\ell$ field multiplications still makes it extremely likely that the second method wins. (Estimates are finger-in-the-air). Sep 17 at 17:11