Skip to main content
Malte Leip

What Are Elliptic Curve Pairings?

An introduction to what pairings are and how they are motivated, with a particular focus on elliptic curve pairings.
Article heading

Pairings, particularly in the context of elliptic curves, have become an important cryptographic building block. In particular, pairings are used in popular zero-knowledge–proof protocols, enabling a wide variety of applications. They are also the crucial ingredient allowing fast aggregation of BLS signatures. These signatures are used by Ethereum, with efficient aggregation being essential for scaling to a high number of validators.

But what are pairings? This article is the first of a two-part series and offers an introduction to what pairings are and what problem they solve. In the second installment, we will then look at concrete applications, such as BLS signatures and the KZG commitment scheme that is used in some ZK proof systems.

We assume that the reader has basic familiarity with concepts like abelian groups, finite fields, and elliptic curves.

One-way Functions

In order to build up step-by-step to the definition of pairings, we start with more basic cryptographic primitives. Many cryptographic constructions rely on a one-way function: a map φ:XY\varphi: X \to Y that is easy to compute but difficult to invert. For example, in the context of cryptographic hash functions, this is exactly the crucial property of preimage resistance.1

Generic Example: Abelian Groups

As a general example, assume that GG is a cyclic abelian group of order nn and gGg \in G a generator. Then, we can consider the map φ:Z/nZG\varphi: \mathbb{Z}/n\mathbb{Z} \to G that is defined by φ(a+nZ)=ag\varphi(a + n\mathbb{Z}) = a\cdot g. If computation of addition in GG is fast, then φ\varphi can be computed efficiently.2 However, while computation of the inverse of φ\varphi can be done efficiently for some examples, it is expected to be computationally intractable in others. The problem of computing φ1(h)\varphi^{-1}(h) for an element hGh \in G is called the discrete logarithm problem.

Let's take a look at a few concrete examples that are of this generic form.

Concrete Example 1: Integers Modulo nn

A trivial example would be the identity map φ:Z/nZZ/nZ\varphi: \mathbb{Z}/n\mathbb{Z} \to \mathbb{Z}/n\mathbb{Z}, with φ(x)=x\varphi(x) = x. In this case, φ\varphi is its own inverse, so the discrete logarithm problem is very easy.

Concrete Example 2: Multiplicative Subgroups of the Integers Modulo a Prime

Consider Z/pZ\mathbb{Z}/p\mathbb{Z}, integers modulo a prime pp. By (Z/pZ)×\left(\mathbb{Z}/p\mathbb{Z}\right)^{\times}, we mean the multiplicative group of units,3 which in this case means all elements except 0+pZ0+p\mathbb{Z} and with group structure given by multiplication modulo pp. Let gg be an element of (Z/pZ)×\left(\mathbb{Z}/p\mathbb{Z}\right)^{\times} that is of order nn,4 and let G=g={g0,g1,,gn1}G=\langle g \rangle = \{g^0, g^1, \dots, g^{n-1}\} be the subgroup that is multiplicatively generated by gg. Then, we can consider φ:Z/nZG\varphi: \mathbb{Z}/n\mathbb{Z} \to G given by φ(a+nZ)=ga\varphi(a + n\mathbb{Z}) = g^a. In this case, we use multiplicative notation for GG, so this example can also serve as an illustration for why the problem of computing the inverse of φ\varphi is called the discrete logarithm problem.

Concrete Example 3: Elliptic Curves

Let EE be the points of an elliptic curve as an abelian group, gg an element of order nn of EE, and GG the subgroup of EE generated by gg. Then φ:Z/nZG\varphi: \mathbb{Z}/n\mathbb{Z} \to G with φ(a+nZ)=ag\varphi(a + n\mathbb{Z}) = a\cdot g is an example. The problem of computing preimages is called the elliptic curve discrete logarithm problem (ECDLP). Computational intractability of the ECDLP is the main assumption made in many elliptic-curve–based cryptographic systems.5

Linear One-way Functions

The generic example we gave above (and hence the three concrete instances we discussed), have the property that φ\varphi is not just a map of sets but a homomorphism of abelian groups, that is, φ\varphi satisfies φ(a+b)=φ(a)+φ(b)\varphi(a + b) = \varphi(a) + \varphi(b). This has the interesting consequence that we can check additive relations in Z/nZ\mathbb{Z}/n\mathbb{Z} even if we only know the images of the involved elements under φ\varphi. Concretely, suppose someone has some integers aa, bb, and cc, gives us φ(a)\varphi(a), φ(b)\varphi(b), and φ(c)\varphi(c), and claims that c=a+bc = a+b. If it is computationally intractable to compute φ1\varphi^{-1}, then we will not be able to recover aa, bb, or cc in order to check this directly. However, as φ\varphi is injective in our examples, c=a+bc = a + b holds if and only if φ(c)=φ(a+b)\varphi(c) = \varphi(a + b). And due to φ\varphi being additive, we can actually compute the right-hand side as φ(a)+φ(b)\varphi(a) + \varphi(b).

Linear Relations

It is clear that we could repeat the previous example with more summands as well. More generally, we can check every linear relation using the images under φ\varphi. If c=(c1,,cm)Z×m\vec{c}=(c_1, \dots, c_m) \in \mathbb{Z}^{\times m} is an mm-tuple of integers and (g1,,gn)(g_1, \dots, g_n) elements of some abelian group, we can write c(g1,,gm)\vec{c} \cdot (g_1, \dots, g_m) for the group element i=1mcigi\sum_{i=1}^{m} c_i \cdot g_i. Let us write c\vec{c} \cdot {-} for the map that sends (g1,,gm)(g_1, \dots, g_m) to c(g1,,gm)\vec{c} \cdot (g_1, \dots, g_m). Then, the main observation is that the following diagram commutes.

(Z/nZ)×mφ×mG×mccZ/nZφG\begin{equation} \begin{CD} \left(\mathbb{Z}/n\mathbb{Z}\right)^{\times m} @>\varphi^{\times m}>> G^{\times m} \\ @V\vec{c}\cdot {-}VV @VV\vec{c}\cdot {-}V \\ \mathbb{Z}/n\mathbb{Z} @>>\varphi> G \end{CD} \end{equation}

Let us unpack what this means. The notation G×mG^{\times m} refers to the mm-fold Cartesian product of GG, so elements are nn-tuples (g1,,gm)\left(g_1, \dots, g_m\right) with giGg_i \in G. Correspondingly, the notation φ×n\varphi^{\times n} refers to the map that applies φ\varphi in each component and thus maps an element (a1,,am)\left(a_1, \dots, a_m\right) of (Z/nZ)×m\left(\mathbb{Z}/n\mathbb{Z}\right)^{\times m} to (φ(x1),,φ(xm))\left(\varphi\left(x_1\right), \dots, \varphi\left(x_m\right)\right). That the diagram commutes means that φ(c)=(c)φ×n\varphi \circ \left(\vec{c} \cdot {-}\right) = \left(\vec{c} \cdot {-}\right) \circ \varphi^{\times n}, so the composites from the top left to the bottom right are the same, no matter which path we choose. The following diagram illustrates where an element (x1,,xm)\left(x_1, \dots, x_m\right) in (Z/nZ)×m\left(\mathbb{Z}/n\mathbb{Z}\right)^{\times m} is mapped to in the other groups. Equality in the bottom right is what it means for the diagram to commute.

Your Image

So now, if someone has a tuple (x1,,xm)(Z/nZ)×m\left(x_1,\dots, x_m\right) \in \left(\mathbb{Z}/n\mathbb{Z}\right)^{\times m} in the top left and claims that the image on the bottom left c(x1,,xm)\vec{c} \cdot \left(x_1,\dots, x_m\right) is equal to some value yy, then we can check this even if we are only given the respective images on the right — (φ(x1),,φ(xm))\left(\varphi(x_1),\dots, \varphi(x_m)\right) in the top right and φ(y)\varphi(y) in the bottom right — by checking whether c(φ(x1),,φ(xm))=φ(y)\vec{c} \cdot \left(\varphi(x_1),\dots, \varphi(x_m)\right) = \varphi(y).

A practical example where checking linear relations like this is used in the context of the third concrete example above (elliptic curves) is ECDSA signature verification.

From Linear to Bilinear

What if we are not satisfied with only checking linear relations? The next step would be to verify quadratic relations, where one of the easiest examples would be ab=ca\cdot b = c, for a,b,cZ/nZa,b,c\in\mathbb{Z}/n\mathbb{Z}. If we want to do this similarly as before, it would be useful if we had φ(xy)=φ(x)φ(y)\varphi(x\cdot y) = \varphi(x) \cdot \varphi(y). However, the right-hand side isn't even defined in general, as GG was just an abelian group (not a ring). For example, what would it mean to multiply two points on an elliptic curve?

The reframing we did using commutative diagram (1) might help us out, though. Note how we are not actually using the knowledge that the bottom map in diagram (1) is the same φ\varphi as the φ\varphi in the top map; it is only relevant that the diagram commutes. So it would already be enough if we had a commutative diagram like so.

Z/nZ×Z/nZφ×φG×G(x,y)xyeZ/nZψH\begin{CD} \mathbb{Z}/n\mathbb{Z} \times \mathbb{Z}/n\mathbb{Z} @>\varphi \times \varphi>> G \times G \\ @V(x,y) \mapsto x\cdot y VV @VVeV \\ \mathbb{Z}/n\mathbb{Z} @>>\psi> H \end{CD}

Here, HH is some other cyclic abelian group of order nn, with ψ:a+nZah\psi: a + n\mathbb{Z} \mapsto a\cdot h for hh a generator of HH, and ee is some map.

Actually, we don't even need the two φ\varphi on the top to be the same, so let us just use φ1\varphi_1, φ2\varphi_2, and φ3\varphi_3, all of which are as in our generic example, so that the following diagram commutes, where ee is some map.

Z/nZ×Z/nZφ1×φ2G1×G2(x,y)xyeZ/nZφ3G3\begin{equation} \begin{CD} \mathbb{Z}/n\mathbb{Z} \times \mathbb{Z}/n\mathbb{Z} @>\varphi_1 \times \varphi_2>> G_1 \times G_2 \\ @V(x,y) \mapsto x\cdot y VV @VVeV \\ \mathbb{Z}/n\mathbb{Z} @>>\varphi_3> G_3 \end{CD} \end{equation}

If we had this, and someone claimed that c=abc = a \cdot b for a,b,cZ/nZa,b,c \in \mathbb{Z}/n\mathbb{Z}, giving us φ1(a)\varphi_1(a), φ2(b)\varphi_2(b), and φ3(c)\varphi_3(c), we could check this by verifying whether e(φ1(a),φ2(b))=φ3(c)e\left(\varphi_1(a), \varphi_2(b)\right) = \varphi_3(c). This works, as commutativity of the diagram implies e(φ1(a),φ2(b))=φ3(ab)e\left(\varphi_1(a), \varphi_2(b)\right) = \varphi_3(a\cdot b) and φ3\varphi_3 is injective.

There is also a slightly different way to use diagram (2). Suppose we are given φ1(a)\varphi_1(a), φ2(b)\varphi_2(b), and φ1(c)\varphi_1(c) instead of φ1(a)\varphi_1(a), φ2(b)\varphi_2(b), and φ3(c)\varphi_3(c) as before. Then as e(φ1(a),φ2(b))=φ3(ab)e\left(\varphi_1(a), \varphi_2(b)\right) = \varphi_3\left(a \cdot b\right) and e(φ1(c),φ2(1))=φ3(c1)=φ3(c)e\left(\varphi_1(c), \varphi_2(1)\right) = \varphi_3\left(c \cdot 1\right) = \varphi_3\left(c\right), injectivity of φ3\varphi_3 again implies that we can check c=abc = a \cdot b by checking e(φ1(a),φ2(b))=e(φ1(c),φ2(1))e\left(\varphi_1(a), \varphi_2(b)\right) = e\left(\varphi_1(c), \varphi_2(1)\right). This variant has the advantage that we are given elements of only G1G_1 and G2G_2 but not additionally of G3G_3 as in the previous variant.

Pairings

Pairings can now informally be defined as maps e:G1×G2G3e: G_1 \times G_2 \to G_3 that fit into a diagram like (2). More precisely, we define a pairing6 to be a map e:G1×G2G3e: G_1 \times G_2 \to G_3 (where G1G_1, G2G_2, and G3G_3 are abelian groups) with the following properties:

  1. Bilinearity:7 e(a+a,b)=e(a,b)+e(a,b)e(a+a', b) = e(a,b) + e(a', b) and e(a,b+b)=e(a,b)+e(a,b)e(a, b+b') = e(a, b) + e(a, b').
  2. Nondegeneracy: If aG1a \in G_1 is such that for every bG2b\in G_2 it holds that e(a,b)=0e(a, b) = 0, then a=0a=0. Analogously, if bG2b \in G_2 is such that for every aG1a \in G_1 it holds that e(a,b)=0e(a, b) = 0, then b=0b=0.

The term bilinear can be explained by the condition being that ee must be linear in the first and second factor separately.

The informal description indeed corresponds to this if we restrict to abelian groups G1G_1, G2G_2, and G3G_3 that are cyclic of order nn. For example, if ee is as in diagram (2), then we can check linearity in the first factor as follows, using commutativity of the diagram and the fact that φ1\varphi_1, φ2\varphi_2, and φ3\varphi_3 are linear and invertible.

e(a+a,b)=e(φ1(φ11(a+a)),φ2(φ21(b)))=(e(φ1×φ2))((φ11(a+a),φ21(b)))=φ3(φ11(a+a)φ21(b))=φ3(φ11(a)φ21(b))+φ3(φ11(a)φ11(b))=e(φ1(φ11(a)),φ2(φ21(b)))+e(φ1(φ11(a)),φ2(φ21(b)))=e(a,b)+e(a,b)\begin{align*} e(a+a', b) &= e\left(\varphi_1\left(\varphi_1^{-1}(a+a')\right), \varphi_2\left(\varphi_2^{-1}(b)\right)\right) \\ &= \left(e \circ (\varphi_1 \times \varphi_2)\right)\left(\left(\varphi_1^{-1}(a+a'),\varphi_2^{-1}(b)\right)\right) \\ &= \varphi_3\left(\varphi_1^{-1}(a+a') \cdot \varphi_2^{-1}(b)\right) \\ &= \varphi_3\left(\varphi_1^{-1}(a) \cdot \varphi_2^{-1}(b)\right) + \varphi_3\left(\varphi_1^{-1}(a') \cdot \varphi_1^{-1}(b)\right) \\ &= e\left(\varphi_1\left(\varphi_1^{-1}(a)\right), \varphi_2\left(\varphi_2^{-1}(b)\right)\right) + e\left(\varphi_1\left(\varphi_1^{-1}(a')\right), \varphi_2\left(\varphi_2^{-1}(b)\right)\right) \\ &= e\left(a, b\right) + e\left(a', b\right) \\ \end{align*}

Conversely, given a bilinear and nondegenerate e:G1×G2G3e: G_1 \times G_2 \to G_3, one can construct a diagram similar to (2) by taking any invertible linear maps φ1\varphi_1 and φ2\varphi_2 and defining φ3\varphi_3 as follows.

φ3(x)e(φ1(x),φ2(1))\varphi_3(x) \coloneqq e\left(\varphi_1(x), \varphi_2(1)\right)

Linearity of φ3\varphi_3 then follows from ee being linear in the first factor and invertibility from ee being nondegenerate. Commutativity of the diagram follows from ee being linear in the second factor.

Pairings for Elliptic Curves

We have now discussed what kind of ee we would like to have, but do usable such maps actually exist? Note that for the cryptographic applications, we would like ee to fit into a diagram similar to (2),8 where ee, φ1\varphi_1, φ2\varphi_2, and φ3\varphi_3 are efficient to compute, but it is computationally intractable to invert φ1\varphi_1, φ2\varphi_2, and φ3\varphi_3, so we cannot just take the multiplication map Z/pZ×Z/pZZ/pZ\mathbb{Z}/p\mathbb{Z} \times \mathbb{Z}/p\mathbb{Z} \to \mathbb{Z}/p\mathbb{Z} as ee and the identity maps for φ1\varphi_1, φ2\varphi_2, and φ3\varphi_3. Luckily there exist usable pairings in the context of elliptic curves. However, we will not get a pairing that is just, for example, E×EGE\times E' \to G for elliptic curves EE and EE' over Fp\mathbb{F}_p. Instead, we get pairings that look like

en:E(Fqk(q,r))[r]×E(Fqk(q,r))[r]μr\begin{equation} e_n: E\left(\mathbb{F}_{q^{k(q,r)}}\right)[r] \times E\left(\mathbb{F}_{q^{k(q,r)}}\right)[r] \to \mu_r \end{equation}

so we will spend the next couple of subsections explaining the notation used. We will start by explaining the meaning of the parentheses, so of notation of the form E(K)E(K). Next we will define the notation μr\mu_r and k(q,r)k(q,r). Finally, we will explain the meaning of the square brackets [r][r].

The KK-Points of Elliptic Curves

Let qq be a prime power and EE an elliptic curve defined over Fq\mathbb{F}_{q}. In many applications of elliptic curves, qq is a prime, and one considers only the Fq\mathbb{F}_q-points of EE, perhaps denoting them by EE as well by abuse of notation. This means concretely9 that if EE is, for example, given by some equation like y2=x3+ax+by^2 = x^3 + a\cdot x + b (with aa and bb elements of Fq\mathbb{F}_q, which is what it means that EE is defined over Fq\mathbb{F}_q), then we consider pairs (x,y)(x, y) that satisfy this equation and where xx and yy are elements of Fq\mathbb{F}_q as well.

However, if KK is a field extension10 of Fq\mathbb{F}_q, then we can also consider xx and yy that are elements of KK and satisfy the equation. We call such a pair (x,y)(x,y) a KK-point of EE and denote the abelian group of KK-points by E(K)E(K).

To explain what E(Fqk(q,r))E\left(\mathbb{F}_{q^{k(q,r)}}\right) from equation (3) is, we are now only missing k(q,r)k(q,r), which we will define next.

Embedding Degree

Suppose that EE is as before and nn is an integer coprime to qq that divides E(Fq)\left|E(\mathbb{F}_q)\right|, the number of Fq\mathbb{F}_q-points of EE. Then, in this setting, the embedding degree refers to the smallest integer k(q,n)>0k(q,n)>0 so that nn divides qk(q,n)1q^{k(q,n)} - 1. Nearly always, qq and nn will be clear from context, and one just writes kk for k(q,n)k(q,n).

One important alternative description is that k(q,n)k(q,n) is the smallest integer so that all nn-th roots of unity (this means solutions of xn=1x^n = 1) are in Fqk\mathbb{F}_{q^k}. The subset of nn-th roots of unity of Fqk\mathbb{F}_{q^k} will be denoted by μn\mu_n. It can be given the structure of an abelian group by multiplication, as if x,yμnx, y \in \mu_n, then (xy)n=xnyn=11=1(xy)^n = x^ny^n = 1 \cdot 1 = 1 and (x1)n=(xn)1=11=1\left(x^{-1}\right)^{n} = \left(x^n\right)^{-1} = 1^{-1} = 1.

So now we know what the codomain of ene_n in (3) is, and to understand the domain, the only thing remaining is what [r][r] means.

Torsion Points

If GG is an abelian group, we can consider the elements gg of GG that satisfy ng=0n\cdot g = 0. Such elements are often called nn-torsion elements, or elements of exponent nn. The set of all nn-torsion elements of GG forms a subgroup of GG that is sometimes denoted by G[n]G[n].

In the situation we were in before, if m1m \geq 1, we can now consider E(Fqm)[n]E(\mathbb{F}_{q^m})[n] the nn-torsion elements among the Fqm\mathbb{F}_{q^m}-points of EE. If d1d \geq 1, then FqmFqmdF_{q^{m}} \subseteq F_{q^{md}}, and we can consider E(Fqm)E(\mathbb{F}_{q^m}) as a subgroup of E(Fqmd)E(\mathbb{F}_{q^{md}}) as well and hence E(Fqm)[n]E(\mathbb{F}_{q^m})[n] as a subgroup of E(Fqmd)[n]E(\mathbb{F}_{q^{md}})[n]. One could now ask whether E(Fqm)[n]E(\mathbb{F}_{q^m})[n] can get larger and larger when replacing mm with md1md_1, then md1d2md_1d_2, and so on.

However, the answer to this is no. There is a largest such abelian group we can obtain, which we denote by E[n]E[n]. Furthermore, if rr is a prime that does not divide q(q1)q(q-1), then we will already have E(Fqk)[r]=E[r]E(\mathbb{F}_{q^{k}})[r] = E[r], where k=k(q,r)k=k(q,r) is the embedding degree defined in the previous subsection. So in this situation, it suffices to consider solutions in Fqk\mathbb{F}_{q^k} of the equation defining the elliptic curve in order to capture all rr-torsion points.

The Weil and Tate Pairings

We can now introduce the first usable pairing in the context of elliptic curves, the Weil pairing. For this, we let EE be an elliptic curve defined over Fq\mathbb{F}_q and nn a positive integer that is coprime to qq. Then the Weil pairing is a pairing as follows.

en:E[n]×E[n]μne_n: E[n]\times E[n] \to \mu_n

To actually be able to compute such a pairing, we use the setup of the previous subsection: instead of a general integer nn, we consider a prime rr that does not divide q(q1)q(q-1). Then ene_n can be considered as a map from E(Fqk)[r]×E(Fqk)[r]E(\mathbb{F}_{q^k})[r] \times E(\mathbb{F}_{q^k})[r] to μn\mu_n, and furthermore μn\mu_n is contained in Fqk\mathbb{F}_{q^k}.

That we need to work with elements of Fqk\mathbb{F}_{q^k} is of course inconvenient if the embedding degree k=k(q,r)k=k(q,r) happens to be large. So why can we not just restrict to E(Fq)×E(Fq)E(\mathbb{F}_q) \times E(\mathbb{F}_q)? We would still have a bilinear map, so why is it important we take all rr-torsion into account? The reason is that this restriction will in general be degenerate and hence not usable for our purposes.

The other classical pairing in this context is the (modified) Tate pairing (or Tate-Lichtenbaum pairing). Again, we let EE be an elliptic curve defined over Fq\mathbb{F}_q and nn a positive integer. Then the modified Tate-Lichtenbaum pairing is a pairing

τn:E(Fqk)[n]×E(Fqk)/nE(Fqk)μn\tau_n: E(\mathbb{F}_{q^k})[n] \times E(\mathbb{F}_{q^k})/nE(\mathbb{F}_{q^k}) \to \mu_n

where k=k(q,n)k=k(q,n) is the embedding degree. Here, the notation E(Fqk)/nE(Fqk)E(\mathbb{F}_{q^k})/nE(\mathbb{F}_{q^k}) means we are considering elements of E(Fqk)E(\mathbb{F}_{q^k}) only modulo elements of the form nPn\cdot P.

Both the Weil and Tate-Lichtenbaum pairings can be efficiently computed in practice using Miller's algorithm. In practice, the pairings most used are (optimal) Ate pairings. These are variants of the Tate pairing that allow for faster computation, and for which, one can reduce the degree of the field extension that one needs to work over in the domain (so that one, for example, can make do with Fq2\mathbb{F}_{q^2} instead of Fq12\mathbb{F}_{q^{12}}), using twists.

From the above, it seems like a low embedding degree would be very useful to make computation of the pairing we choose more efficient by avoiding use of a larger field. However, there is a flip side to this, as we will see in the next section.

MOV and Frey-Rück Attacks

Let EE be an elliptic curve defined over Fq\mathbb{F}_q. Suppose we are given two points PP and QQ in E(Fq)E(\mathbb{F}_q) so that PP is of prime order rr and there is an mZm\in\mathbb{Z} so that Q=mPQ = m\cdot P. Recovering mm modulo rr from PP and QQ is the ECDLP we already mentioned towards the beginning of this article, and computational intractability of this problem is crucial for many cryptographic systems based on elliptic curves.

Now assume that rr does not divide q(q1)q(q-1), and we can find a point TT in E(Fqk(q,n))E(\mathbb{F}_{q^{k(q, n)}}) so that TT is of order rr and er(P,T)1e_r(P, T) \neq 1. By bilinearity of ere_r we have the following.

er(Q,T)=er(mP,T)=er(P,T)me_r(Q, T) = e_r(m\cdot P, T) = e_r(P, T)^m

Finding mm modulo rr so that er(Q,T)=er(P,T)me_r(Q, T) = e_r(P, T)^m is exactly the DLP in Fqk(q,r)×\mathbb{F}_{q^{k(q, r)}}^{\times}. Finding a TT that satisfies the assumption is easy in practice, so this method reduces the original ECDLP to a DLP in Fqk(q,r)×\mathbb{F}_{q^{k(q, r)}}^{\times}.

The method just described is called the MOV attack after the authors Menezes, Okamoto, and Vanstone. The Frey-Rück attack is similar but employs the Tate pairing.

Now for both the ECDLP and the above DLP, no algorithm is known that solves them in polynomial time. However, solving a DLP in Fqa\mathbb{F}_{q^a} using the index calculus algorithm is faster than solving the ECDLP in E(Fqa)E(\mathbb{F}_{q^a}) using the fastest generic available algorithm, the baby-step giant-step algorithm. This means that in the situation above, the ECDLP can be solved faster than expected if the embedding degree k=k(q,r)k=k(q, r) is small.

If we wish to make use of pairing-based cryptography, we must thus use an elliptic curve with a carefully selected embedding degree — large enough to ensure the required security level for the ECDLP but otherwise as small as possible to ensure that the pairing can be computed efficiently. The embedding degrees chosen in practice for use with pairings are usually in the range from 66 to 2424 or so, with 1212 a popular choice.

Conclusion

We have defined pairings and motivated why they might be useful and also looked at the form that pairings for elliptic curves take.

In the second (and final) installment of this article series, we are going to take a closer look at cryptographic applications of pairings. In particular, we are going to explain BLS signatures, including how they can be aggregated, which is a highly useful property enabling Ethereum to scale to a high number of validators. We are also going to discuss KZG polynomial commitments, which are a building block used in ZK proof systems such as Halo2.

About Us

Zellic specializes in securing emerging technologies. Our security researchers have uncovered vulnerabilities in the most valuable targets, from Fortune 500s to DeFi giants.

Developers, founders, and investors trust our security assessments to ship quickly, confidently, and without critical vulnerabilities. With our background in real-world offensive security research, we find what others miss.

Contact us for an audit that’s better than the rest. Real audits, not rubber stamps.

Footnotes

  1. We require additional properties from cryptographic hash functions, such as collision resistance. These will not play a role in the rest of this article, though.

  2. Using the double-and-add method.

  3. A unit is an element of a ring that has a multiplicative inverse.

  4. That gg has order nn means that gn=1+qZg^n = 1 + q\mathbb{Z} and gk1+qZg^k \neq 1 + q\mathbb{Z} for 1k<n1 \leq k < n.

  5. Whether the ECDLP can be solved efficiently depends, in particular, on the curve EE. For example, if EE is an anomalous curve, then an efficient algorithm exists.

  6. What we call pairings here are also sometimes called bilinear pairings or nondegenerate bilinear maps.

  7. To be precise, this is Z\Z-bilinearity.

  8. We relax the requirement that φi\varphi_i must be isomorphisms and that their domain must be exactly Z/nZ\mathbb{Z}/n\mathbb{Z}.

  9. The following description is simplified, for example, by ignoring the point at infinity. But discussing the Proj construction is out of scope for this post.

  10. That KK is a field extension of Fq\mathbb{F}_q means that Fq\mathbb{F}_q is a subfield of KK (that is, a subset with the same addition and multiplication). For our purposes, it suffices to think of the case K=FqmK=\mathbb{F}_{q^m} for m1m\geq 1