Join Log in
Score:1
avatar Crypto

Multiplication of pairings vs. exponentiation of the group elements

cn flag
A.Solei

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?

51
0 + 0
kr flag
Mehdi Tibouchi
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](https://link.springer.com/content/pdf/10.1007%2F3-540-45537-X_13.pdf) techniques to further greatly speed up the computation of $\prod_i \textit{pk}_i^{a_i}$ compared to naively doing $n$ exponentiations and products.
2
Reply
poncho avatar
my flag
poncho
@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?
0
Reply
Daniel S avatar
ru flag
Daniel S
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).
0
Reply
ธงชาติไทย
Elon Musk
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.