4
$\begingroup$

I'm just curious why do we use pairings on elliptic curve cryptography. There is a lot of information about how to use it, but I cannot find information about why to use it. Can somebody help?

$\endgroup$
  • $\begingroup$ Your question seems overly broad. Do you mean specifically pairings on elliptic curves vs pairings some other way? Or are you more interested in the applications of pairings. $\endgroup$ – mikeazo Mar 12 '18 at 15:44
  • $\begingroup$ @mikeazo, Thank you for the question. I meant application of pairings on elliptic curves. Why should we use it at all? Maybe for the improvement of the performance, or is there another reason? $\endgroup$ – lol lol Mar 12 '18 at 15:48
  • 2
    $\begingroup$ The applications people are developing using elliptic curve pairings were impossible until elliptic curve pairings were discovered. Things like identity based signatures, identity/attribute based encryption. $\endgroup$ – mikeazo Mar 12 '18 at 16:05
10
$\begingroup$

Although the question is a bit broad, I think it's an interesting one.

Giving a bit of context helps with the explanations. In the 80's, many cryptographic primitives have been design, based on group structures (usually relying on variants of the discrete logarithm assumption over this group). The rationale behind the initial introduction of elliptic curves in cryptography was the following: over a group with no additional structure, solving discrete log is hard (we say that discrete log is "hard in the generic group model"). Elliptic curves are groups, yet they seemed to have little, if any, additional structure that one could exploit to solve the discrete log problem (and related problems).

In the 90's, an apparent weakness was discovered in many types of elliptic curves: in some curves, people observed that there was in fact more structure than expected, as there was an operation that could move (in polynomial time) the discrete log problem from the curve, to a target space (as you can guess, this operation is the pairing operation). Therefore, when the target space was a space with a lot of structure (such as a field), this allowed to reduce solving a hard problem (dlog over a curve) to a considerably easier one (dlog over fields). A variety of attacks were developed, based on the computation of these pairings.

Then, in the 2000's, Boneh and Franklin on one side, and Joux on the other, came up with the idea that this apparent weakness could become a feature: intuitively, a pairing allows to "multiply" the exponents of two group elements, while the usual group structure only allows to add an substract exponents. To do so, one had to use a curve where the pairing was not a strong weakness (i.e., a pairing moving the discrete log to a group sufficiently large to make the computation of dlog still infeasible in the target group). Then, they came up respectively with the following applications:

  • Identity based encryption, which was a long standing open problem. One can obtain very efficient instantiations using pairings. It has recently been shown that standard groups (without pairings) suffice for identity-based encryption; however, pairing-based solutions remain considerably more efficient.
  • Tripartite non-interactive key exchange. Here, the idea is simple: the standard two-party DH key exchange works by exchanging two group elements, $g^a$ and $g^b$, and letting the two players locally compute $g^{ab}$. If one has a pairing, we can add a third player without further interaction: the players exchange $(g^a,g^b,g^c)$, and can locally compute $K = e(g,g)^{abc}$, where $e$ is the pairing operation.

This last example is perhaps the most useful one for you, because it illustrate on (arguably) the simplest possible scenario the reason why the additional structure given by a pairing allows for new applications. Following the above applications, many more have been discovered, which can be obtained from pairing but not (or not efficiently) without them. This includes:

... and many more. In addition to the "multiplication in the exponent" allowed by pairings, another feature which is at the core of many applications is the fact that they allow to build a gap group, i.e., a group in which the decision problem (DDH) is easy, but the search problem (CDH) remains hard. Such gap groups have many applications (e.g. identity-based signatures, undeniable signatures...).

$\endgroup$
  • $\begingroup$ You are welcome. If it answered your question, you should consider accepting it :) $\endgroup$ – Geoffroy Couteau Mar 13 '18 at 11:41
  • $\begingroup$ Sorry for a delay! Accepted :) $\endgroup$ – lol lol Mar 13 '18 at 13:07

Your Answer

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

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