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$ ↩