What Are Elliptic Curve Pairings?

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 $\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.¹

Generic Example: Abelian Groups​

As a general example, assume that $G$ is a cyclic abelian group of order $n$ and $g \in G$ a generator.
Then, we can consider the map $\varphi: \mathbb{Z}/n\mathbb{Z} \to G$ that is defined by $\varphi(a + n\mathbb{Z}) = a\cdot g$.
If computation of addition in $G$ is fast, then $\varphi$
can be computed efficiently.² 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 $\varphi^{-1}(h)$ for an element $h \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 $n$​

A trivial example would be the identity map $\varphi: \mathbb{Z}/n\mathbb{Z} \to \mathbb{Z}/n\mathbb{Z}$,
with $\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 $\mathbb{Z}/p\mathbb{Z}$, integers modulo a prime $p$.
By $\left(\mathbb{Z}/p\mathbb{Z}\right)^{\times}$, we mean the multiplicative group of units,³
which in this case means all elements except $0+p\mathbb{Z}$ and with group structure given
by multiplication modulo $p$. Let $g$ be an element of $\left(\mathbb{Z}/p\mathbb{Z}\right)^{\times}$
that is of order $n$,⁴
and let $G=\langle g \rangle = \{g^0, g^1, \dots, g^{n-1}\}$ be the subgroup that is multiplicatively generated by $g$.
Then, we can consider $\varphi: \mathbb{Z}/n\mathbb{Z} \to G$ given by
$\varphi(a + n\mathbb{Z}) = g^a$.
In this case, we use multiplicative notation for $G$, 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 $E$ be the points of an elliptic curve as an abelian group,
$g$ an element of order $n$ of $E$, and $G$ the subgroup of
$E$ generated by $g$. Then $\varphi: \mathbb{Z}/n\mathbb{Z} \to G$
with $\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.⁵

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
$\varphi(a + b) = \varphi(a) + \varphi(b)$.
This has the interesting consequence that we can check additive relations in $\mathbb{Z}/n\mathbb{Z}$
even if we only know the images of the involved elements under $\varphi$.
Concretely, suppose someone has some integers $a$, $b$, and $c$, gives us
$\varphi(a)$, $\varphi(b)$, and $\varphi(c)$, and claims that $c = a+b$.
If it is computationally intractable to compute $\varphi^{-1}$, then we will
not be able to recover $a$, $b$, or $c$ in order to check this directly.
However, as $\varphi$ is injective in our examples, $c = a + b$ holds if and
only if $\varphi(c) = \varphi(a + b)$. And due to $\varphi$ being additive,
we can actually compute the right-hand side as $\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 $\vec{c}=(c_1, \dots, c_m) \in \mathbb{Z}^{\times m}$ is an $m$-tuple
of integers and $(g_1, \dots, g_n)$ elements of some abelian group, we
can write $\vec{c} \cdot (g_1, \dots, g_m)$ for the group element
$\sum_{i=1}^{m} c_i \cdot g_i$. Let us write $\vec{c} \cdot {-}$ for the map
that sends $(g_1, \dots, g_m)$ to $\vec{c} \cdot (g_1, \dots, g_m)$.
Then, the main observation is that the following diagram commutes.

$$\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^{\times m}$ refers to the $m$-fold Cartesian product of $G$, so elements are
$n$-tuples $\left(g_1, \dots, g_m\right)$ with $g_i \in G$.
Correspondingly, the notation $\varphi^{\times n}$ refers to the map that applies
$\varphi$ in each component and thus maps an element
$\left(a_1, \dots, a_m\right)$ of $\left(\mathbb{Z}/n\mathbb{Z}\right)^{\times m}$
to
$\left(\varphi\left(x_1\right), \dots, \varphi\left(x_m\right)\right)$.
That the diagram commutes means that
$\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
$\left(x_1, \dots, x_m\right)$ in
$\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.

So now, if someone has a tuple $\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 $\vec{c} \cdot \left(x_1,\dots, x_m\right)$
is equal to some value $y$, then we can check this even if we are only given the respective images
on the right — $\left(\varphi(x_1),\dots, \varphi(x_m)\right)$ in the top right and $\varphi(y)$ in the
bottom right — by checking whether $\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 $a\cdot b = c$, for $a,b,c\in\mathbb{Z}/n\mathbb{Z}$.
If we want to do this similarly as before, it would be useful if we had
$\varphi(x\cdot y) = \varphi(x) \cdot \varphi(y)$.
However, the right-hand side isn’t even defined in general, as $G$
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.

$$\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, $H$ is some other cyclic abelian group of order $n$, with $\psi: a + n\mathbb{Z} \mapsto a\cdot h$ for $h$ a generator of $H$, and $e$ is some map.

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

$$\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 = a \cdot b$ for $a,b,c \in \mathbb{Z}/n\mathbb{Z}$,
giving us $\varphi_1(a)$, $\varphi_2(b)$, and $\varphi_3(c)$, we could check this
by verifying whether $e\left(\varphi_1(a), \varphi_2(b)\right) = \varphi_3(c)$.
This works, as commutativity of the diagram implies
$e\left(\varphi_1(a), \varphi_2(b)\right) = \varphi_3(a\cdot b)$
and $\varphi_3$ is injective.

There is also a slightly different way to use diagram (2). Suppose we are given
$\varphi_1(a)$, $\varphi_2(b)$, and $\varphi_1(c)$ instead
of $\varphi_1(a)$, $\varphi_2(b)$, and $\varphi_3(c)$ as before.
Then as
$e\left(\varphi_1(a), \varphi_2(b)\right) = \varphi_3\left(a \cdot b\right)$
and
$e\left(\varphi_1(c), \varphi_2(1)\right) = \varphi_3\left(c \cdot 1\right) = \varphi_3\left(c\right)$,
injectivity of $\varphi_3$ again implies that we can check $c = a \cdot b$
by checking
$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 $G_1$
and $G_2$ but not additionally of $G_3$ as in the previous variant.

Pairings​

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

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

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

The informal description indeed corresponds to this if we restrict to abelian
groups $G_1$, $G_2$, and $G_3$ that are cyclic of order $n$.
For example, if $e$ 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 $\varphi_1$, $\varphi_2$, and $\varphi_3$ are linear
and invertible.

$$\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: G_1 \times G_2 \to G_3$,
one can construct a diagram similar to (2) by taking any invertible linear
maps $\varphi_1$ and $\varphi_2$ and defining $\varphi_3$ as follows.

$$\varphi_3(x) \coloneqq e\left(\varphi_1(x), \varphi_2(1)\right)$$

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

Pairings for Elliptic Curves​

We have now discussed what kind of $e$ we would like to have, but do usable such maps actually exist?
Note that for the cryptographic applications, we would like $e$ to fit into a diagram
similar to (2),⁸ where $e$, $\varphi_1$, $\varphi_2$, and $\varphi_3$ are efficient to compute, but
it is computationally intractable to invert $\varphi_1$, $\varphi_2$, and $\varphi_3$,
so we cannot just take the multiplication
map $\mathbb{Z}/p\mathbb{Z} \times \mathbb{Z}/p\mathbb{Z} \to \mathbb{Z}/p\mathbb{Z}$ as $e$
and the identity maps for $\varphi_1$, $\varphi_2$, and $\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\times E’ \to G$ for elliptic curves
$E$ and $E’$ over $\mathbb{F}_p$.
Instead, we get pairings that look like

$$\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)$.
Next we will define the notation $\mu_r$ and $k(q,r)$.
Finally, we will explain the meaning of the square brackets $[r]$.

The $K$-Points of Elliptic Curves​

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

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

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

Embedding Degree​

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

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

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

Torsion Points​

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

In the situation we were in before, if $m \geq 1$, we can now consider
$E(\mathbb{F}_{q^m})[n]$ the $n$-torsion elements among the $\mathbb{F}_{q^m}$-points of $E$.
If $d \geq 1$, then $F_{q^{m}} \subseteq F_{q^{md}}$, and we can consider
$E(\mathbb{F}_{q^m})$ as a subgroup of $E(\mathbb{F}_{q^{md}})$ as well and hence
$E(\mathbb{F}_{q^m})[n]$ as a subgroup of $E(\mathbb{F}_{q^{md}})[n]$.
One could now ask whether $E(\mathbb{F}_{q^m})[n]$ can get larger and larger when
replacing $m$ with $md_1$, then $md_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]$.
Furthermore, if $r$ is a prime that does not divide $q(q-1)$, then we will
already have $E(\mathbb{F}_{q^{k}})[r] = E[r]$, where $k=k(q,r)$ is the embedding
degree defined in the previous subsection. So in this situation, it suffices
to consider solutions in $\mathbb{F}_{q^k}$ of the equation defining the elliptic curve
in order to capture all $r$-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 $E$ be an elliptic curve defined over $\mathbb{F}_q$ and $n$
a positive integer that is coprime to $q$. Then the Weil pairing is
a pairing as follows.

$$e_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 $n$, we consider a prime $r$ that does not
divide $q(q-1)$. Then $e_n$ can be considered as a map from
$E(\mathbb{F}_{q^k})[r] \times E(\mathbb{F}_{q^k})[r]$ to $\mu_n$, and
furthermore $\mu_n$ is contained in $\mathbb{F}_{q^k}$.

That we need to work with elements of $\mathbb{F}_{q^k}$ is of course
inconvenient if the embedding degree $k=k(q,r)$ happens to be large. So why can we not
just restrict to $E(\mathbb{F}_q) \times E(\mathbb{F}_q)$? We would still have
a bilinear map, so why is it important we take all $r$-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 $E$ be an elliptic curve defined over $\mathbb{F}_q$ and $n$
a positive integer. Then the modified Tate-Lichtenbaum pairing is a pairing

$$\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)$ is the embedding degree.
Here, the notation $E(\mathbb{F}_{q^k})/nE(\mathbb{F}_{q^k})$ means we
are considering elements of $E(\mathbb{F}_{q^k})$ only modulo elements
of the form $n\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
$\mathbb{F}_{q^2}$ instead of $\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 $E$ be an elliptic curve defined over $\mathbb{F}_q$. Suppose we
are given two points $P$ and $Q$ in $E(\mathbb{F}_q)$ so that
$P$ is of prime order $r$ and there is an $m\in\mathbb{Z}$ so that $Q = m\cdot P$.
Recovering $m$ modulo $r$ from $P$ and $Q$ 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 $r$ does not divide $q(q-1)$, and
we can find a point $T$ in $E(\mathbb{F}_{q^{k(q, n)}})$
so that $T$ is of order $r$ and $e_r(P, T) \neq 1$.
By bilinearity of $e_r$ we have the following.

$$e_r(Q, T) = e_r(m\cdot P, T) = e_r(P, T)^m$$

Finding $m$ modulo $r$ so that
$e_r(Q, T) = e_r(P, T)^m$
is exactly the DLP in $\mathbb{F}_{q^{k(q, r)}}^{\times}$.
Finding a $T$ that satisfies the assumption is easy in practice, so this method
reduces the original ECDLP to a DLP in $\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 $\mathbb{F}_{q^a}$ using the
index calculus algorithm↗
is faster than solving the ECDLP in $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)$ 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 $6$ to $24$ or so, with $12$ 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.

Endnotes​

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 $g$ has order $n$ means that $g^n = 1 + q\mathbb{Z}$ and $g^k \neq 1 + q\mathbb{Z}$ for $1 \leq k < n$. ↩

5. Whether the ECDLP can be solved efficiently depends, in particular, on the curve $E$. For example, if $E$ 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$-bilinearity. ↩

8. We relax the requirement that $\varphi_i$ must be isomorphisms and that their domain must be exactly $\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 $K$ is a field extension of $\mathbb{F}_q$ means that $\mathbb{F}_q$ is a subfield of $K$ (that is, a subset with the same addition and multiplication). For our purposes, it suffices to think of the case $K=\mathbb{F}_{q^m}$ for $m\geq 1$ ↩

*** This is a Security Bloggers Network syndicated blog from Zellic — Research Blog authored by Zellic — Research Blog. Read the original post at: https://www.zellic.io/blog/what-are-elliptic-curve-pairings