Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

The definition of $e$ can be seen here. I want to know the accurate comparison of efficiency between $e(\cdot,\cdot)$ and $g^a \pmod{p}$. If computing $e(P,Q)$ is less efficient than computing $g^a \pmod{p}$, should we prefer $g^a \pmod{p}$ to $e(P,Q)$ when designing protocols?

Also, what is the reason for defining the pairings on an elliptic curve? Is it to solve the multiplication of points over the elliptic curve?

p.s. Sorry to have a lot of questions, I'm new to elliptic curve cryptography..

share|improve this question
    
Regarding your first question: Acutally, you cannot compare a pairing evaluation to an exponentiation in $Z_p^*$. To be more precise, you should compare it to an exponentiation in $\mathbb{F}_{q^k}^*$ (which depends on the curve/pairing you use). When computing a pairing via Miller's algorithm (you may look here), you always need a final exponentation in the respective field in the pairing computation. So in general: cost(pairng) > cost(exp in field). –  DrLecter Oct 23 '13 at 12:07
    
Pairing and exponentiation in $\mathbb{Z}_p^{*}$ are entirely different operations. The reason for defining pairings is, that they do things which we don't know how to do in the standard "mod p" groups. Additionally, if you want to compare the actual computation time, the security parameters play a huge role. EC is usually done with much shorter numbers, s.t. the EC addition is actually faster than exponentiation in $\mathbb{Z}_p^*$, but pairings are even slower –  tylo Oct 24 '13 at 9:12
    
@DrLecter a small confusion: if $P=(x_1,y_1)$ and $aP=(x_2,y_2)$, can i say that $e(x_2Q,P)\stackrel{?}{=} e(x_1Q,aP) $ –  Alex Oct 27 '13 at 5:28
    
No you cannot. Alex I think you are confusing things here. I guess you speak of affine coordinates of an elliptic curves point when writing $P=(x_1,y_1)$ and of scalar multiplication when writing $aP$. Latter means $P+\ldots+P$ ($a-1$ times). Now you deal scalars and coordinates of points on a curve interchangeable. When looking at how arithmetics on elliptic curve groups is done, see for instance here, then it should be clear that this does not hold. –  DrLecter Oct 28 '13 at 8:38
add comment

1 Answer

up vote 2 down vote accepted

Firstly, there is not one definition of a pairing.

A pairing is a bilinear function: you have three finite groups $G_1$, $G_2$ and $G_3$; a pairing is a function $e$ such that, for all $(g_1,g_2) \in G_1\times G_2$ and all integers $a$ and $b$, then $e(g_1^a,g_2^b) =e(g_1,g_2)^{ab}$ (I am here using multiplicative notation for the three groups). Why would you want such a function, in a cryptographic setting ? Basically, if you can have the following properties together:

  • $G_1$, $G_2$ and $G_3$ have known, finite orders.
  • Computations on these groups is easy.
  • The computational Diffie-Hellman assumption holds on the groups.
  • A pairing function $e$ can be defined and easily computed on these groups.

Then we can use the groups and the pairing function to power some interesting cryptographic protocols, in particular Identity-Based Encryption, which would be hard to obtain without pairing-friendly groups. To state things in a very general way, "normal" groups are for protocols which involve interactions between two parties (e.g. Diffie-Hellman) while pairing-friendly groups are for protocols which involve interactions between three parties.

So the cryptographic question is: do we know pairing-friendly groups ?

Right now, the only practical candidates we have for pairing-friendly groups are some special elliptic curves, which allow for a few distinct pairing functions (Weil, Tate, Ate and Eta pairings, the last two being subvariants of the Tate pairings). So we don't use pairings to "solve things" on elliptic curves; we use elliptic curves so that we can have computable pairings, which open the possibility of nifty advanced protocols.

(Note that initially, Weil and Tate pairings were first investigated as mechanisms to break elliptic curves. Fortunately, usual elliptic curves don't allow for computable pairings -- if you try to apply Weil or Tate pairing on a "normal" curve, you will find that it entails computations on integers which would not fit in the RAM of any computer, even if the computer was as big as the Moon. Pairing-friendly curves are in fact "slightly weakened curves" specially crafted so that pairings are computable, but not to the point that they allow a fast break of the said curves.)

Then there are details. For instance, in some protocols we want a symmetric pairing where $G_1$ and $G_2$ are the same group; while in other protocols we want the opposite: $G_1$ and $G_2$ shall be distinct groups, with, for instance, a one-way morphism from $G_2$ to $G_1$ (but not in the other direction). You will not use the same curves and the same kind of pairing for all cases.

So your question cannot have any simple answer except that "it depends". We can still give orders of magnitude: for a given security level (e.g. that of 2048-bit RSA), usual pairings will entail a computational cost which is about 8 to 12 times the cost of decryption with 2048-bit RSA. Don't try to read too much in that figure, though. What must be remembered is that, for instance, the BLS signature scheme allows for short signatures (shorter than DSA or ECDSA) but implies a computational overhead (for signature verification) which is not necessarily negligible.

share|improve this answer
    
So, roughly speaking, a pairing($e:G\times G \to G_T$)'s computation is equal to 8~12 exponent compution, right? but, recently, I read a paper, in the section 5.4, it says 1 pairing operation is roughly equivalent to 3 exponentiations in computation. So, I feel a little confused about this problem, could you help me to clear this confusion? –  Alex Dec 22 '13 at 15:06
    
Any statement on performance is relative to hardware and implementation characteristics and usage conditions, and thus may vary quite a lot. As I said, "don't try to read too much in that figure". –  Thomas Pornin Dec 22 '13 at 15:14
    
can I say that the bilinear pairing is always defined over super singular elliptic curve group with large element size, so its computation is time-consuming? –  Alex Mar 19 at 9:25
    
No, it is not always defined over a supersingular elliptic curve. It is defined overs "curves of low embedding degree". Supersingular curves have a low embedding degree, but are not alone in that category. However, parts of the computation must occur with elements from a field which is large enough to resist discrete logarithm (DLP, not ECDLP), and that's quite larger than what is used in normal elliptic curves (say, 1200 bits instead of 200), and that means higher computational cost. –  Thomas Pornin Mar 19 at 10:49
    
"or a given security level (e.g. that of 2048-bit RSA), usual pairings will entail a computational cost which is about 8 to 12 times the cost of decryption with 2048-bit RSA", can you show me some related references to support this sentence? –  Alex Apr 15 at 8:42
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.