Why "pairings on elliptic curve" are used?

Question

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?

Answer 1

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:

• Non-interactive zero-knowledge proofs
• Verifiable pseudorandom functions
• Short Signatures

... 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...).