1
$\begingroup$

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?

$\endgroup$
3
  • 2
    $\begingroup$ 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. $\endgroup$ Sep 17 at 16:35
  • $\begingroup$ @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? $\endgroup$
    – poncho
    Sep 17 at 16:53
  • $\begingroup$ 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). $\endgroup$
    – Daniel S
    Sep 17 at 17:11

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.