Applications of Riemann-Roch in cryptography

$$ \def\F{\mathbb{F}} \def\L{\mathcal{L}} \def\C{\mathcal{C}} $$

The Riemann-Roch theorem is a fundamental result in the study of curves. In this post, I’ll go through some of its applications in cryptography.

Divisors and the Riemann-Roch theorem

Let $C$ be an algebraic curve, i.e., a smooth projective variety of dimension one over a field $K$¹. The group of divisors $Div(C)$ is the free abelian group generated by points of $C$, i.e., elements of $Div(C)$ look like $D = \sum_{P\in C} n_P P$ where $n_P\in \mathbb{Z}$ is non-zero for only finitely many $P\in C$.

For functions $0\ne f\in K(C)$ (the function field of the curve), we can define a divisor $div(f) = \sum_{P\in C} ord_P(f) P$ where $ord_P(f)$ is $n>0$ if $f$ has a zero of order $n$ at $P$, $n<0$ if $f$ has a pole of order $-n$ at $P$, $0$ otherwise.

There is a surjective map $Div(C) \to \mathbb{Z}$ called the degree of a divisor and defined by $$\deg(\sum_{P\in C}n_P P) = \sum_{P\in C}n_P.$$ Its kernel is denoted $Div^0(C) = \ker(\deg)$. A standard result is that $div(f) \in Div^0(C)$ for all $f\in \bar{K}(C)$.

We define a partial order on $Div(C)$ by

$$ \sum_{P\in C} n_P P \geq \sum_{P\in C} m_P P \iff n_P \geq m_P \text{ for all } P\in C. $$

The object of study of the Riemann-Roch theorem is the Riemann-Roch space $\mathcal{L}(D)$ for $D\in Div(C)$:

$$ \mathcal{L}(D) = \{f \in K(C)^* \ \mid \ div(f) \geq -D\} \cup {0}. $$

This set has a structure of $K$-vector space and we denote by $\ell(D)$ its dimension. We can now state the Riemann-Roch theorem.

Riemann-Roch Theorem: There is a divisor $K_C$ and an integer $g\geq 0$ such that for all $D\in Div(C)$ $$\ell(D) - \ell(K_C - D) = \deg D - g + 1.$$

The integer $g$ is called the genus of $C$, and the divisor $K_C$ is called a canonical divisor of $C$. There is a rigorous definition of $K_C$ but we won’t need it thanks to the following result

$$ \deg D > 2g-2 \implies \ell(K_C - D) = 0. $$

So for such divisors $D$, the Riemann-Roch theorem is just $$\ell(D) = \deg D - g + 1.$$

Elliptic curves

Weierstrass equation

Elliptic curves are often defined as being sets of points $(x,y) \in K^2$ satisfying a Weierstrass equation

$$ E: y^2 + axy + by = x^3 + cx^2 + dx + e, $$

for some $a,b,c,d,e \in K$. This is a simple definition but it doesn’t give a lot of intuition and it’s not obvious why we should care about solutions of this equation in particular.

A more elegant definition is: an elliptic curve is a curve $E$ of genus $1$ with a distinguished point $O\in E$.

We can use Riemann-Roch to recover the Weierstrass equation. Consider the spaces $\mathcal{L}(n(O))$ for $n>0$. By the Riemann-Roch theorem, we have $\ell(n(O)) = n$ since $g=1$. A basis for $\mathcal{L}((O))$ is just $\{1\}$, and let $\{1,x\}$ be a basis for $\mathcal{L}(2(O))$ and $\{1,x,y\}$ be a basis for $\mathcal{L}(3(O))$, so $x$ has a pole of order $2$ at $O$ and $y$ has a pole of order $3$ at $O$. Then the $7$ functions $1,x,y,x^2,xy,x^3,y^2$ are in $\mathcal{L}(6(O)$ which has dimension $6$. So there must be a non-trivial linear relation

$$ A + Bx + Cy + Dx^2 + Exy + Fx^3+Gy^2 = 0 $$

If either $F$ or $G$ is zero then all terms in the relation have poles at $O$ of distinct order, which is impossible. So $F,G\ne 0$ and by rescaling $x$ and $y$ we get back the Weierstrass equation.

Group structure

One of the main reason elliptic curves are used in cryptography is because the set of points of an elliptic curves has the structure of an abelian group. Using the Weierstrass equation, the group law is usually defined by drawing lines and waving hands. There is, however, a much simpler and equivalent definition. By another application of the Riemann-Roch theorem, one can prove that every $D\in Div^0(E)$ is of the form $D = (P)-(O)+div(f)$ for a unique $P\in E$ and $f\in K(E)$. Moreover, the map

$$ \sigma: Div^0(E) \to E: D \mapsto P $$

is surjective and it’s kernel the set of principal divisors $\{div(f) \ \mid \ f \in K(E)^*\}$. Therefore, $E$ is in bijection with the Picard group $Pic^0(E)$, the group $Div^0(E)$ quotiented by principal divisors. We can thus trivially put an abelian group structure on $E$ by asking that $Pic^0(E) \to E$ is a group isomorphism. Moreover this group structure coincides with the usual group law we all know and love! Additionally, this provides a clean proof that the usual group law is associative, something only the bravest of us prove by hand.

Algebraic geometry codes

Let $C$ be a curve of genus $g$ over a finite field $\F_q$, $G$ be a divisor of $C$ and $P_1,\dots,P_n$ be points of $C$ disjoint from the support of $G$. Then the map

$$ ev: \L(G) \to \F_q^n \newline $$

$$ f \mapsto (f(P_1),\dots,f(P_n)) $$

is well-defined (since $f$ cannot have poles at any $P_i$) and defines a linear code. This construction is called an algebraic geometry code or Goppa code.

Write $\C(G)$ for the image of $ev$. The dimension of this code is the dimension of $\C(G)$, which is the dimension of $\L(G)$, i.e. $\ell(G)$, minus the dimension of $\ker(ev)$ $$ \dim \C(G) = \ell(G) - \dim \ker(ev).$$ The evaluation $ev$ vanishes at functions with zeros of order at least $1$ at every $P_i$. So $\ker(ev) = \L(G-D)$ where $D$ is the divisor $D = P_1 + \dots + P_n$. Therefore, the dimension of the code is $\ell(G) - \ell(G-D)$. By applications of Riemann-Roch, when $2g-2 < \deg G < n$ we can simplify this expression to $$ \dim \C(G) = \deg G + 1 - g.$$

Another interesting parameter of a code is it’s minimal distance, defined as $d\left(\C(G)\right)=\min \{\text{wt}(x) \mid 0 \ne x \in \C(G) \}$, where $\text{wt}(x) = \#\{i \mid x_i\ne 0\}$ is the Hamming weight. Fix $0\ne f \in \L(G)$ with $\text{wt}(ev(f)) = d$. Then, there are $n-d$ points $P_{i_1},\dots,P_{i_{n-d}}$ such that $f(P_{i_j})=0$. Thus, $f$ is in $\L\left(G-(P_{i_1}+\dots+P_{i_{n-d}})\right)$ and so this space has nonzero dimension. Therefore²,

$$ \deg \left( G-(P_{i_1}+\dots+P_{i_{n-d}}) \right) =\deg G - n + d \geq 0, $$

and so $d\left(\C(G)\right) \geq n - \deg G$.

Using the expressions for the dimension $k$ and minimal distance $d$ of the code, we get the inequality

$$ k+d = \deg G + 1 - g + d \geq \deg G + 1 - g + n - \deg G = n+1-g. $$

This can be compared with the Singleton bound saying that $k+d\leq n+1$. This bound is thus achieved when $g=0$ and otherwise is off by at most $g$.

With $g=0$, we also recover Reed-Solomon codes. Indeed, let $C = \mathbb{P}^1$ the projective line, and let $G = m\infty$. Then, functions in $\L(G)$ are just polynomials of degree at most $m$ and $\C(G)$ is the code given by evaluations of such polynomials at $n$ points in $\F_q.$

Therefore algebraic geometry codes can be seen as a generalization of Reed-Solomon codes. One advantage they have on the latter is that Reed-Solomon codes require $q\geq n$ while for algebraic geometry codes, some curves have more than $q$ points and thus can use $n > q$. Here is an example:

F = GF(49)
R.<x,y,z> = F[]
C = Curve(x^8 + y^8 - z^8)
C.genus() # returns 21
sum(a in C for a in ProjectiveSpace(R)) # returns 344 = number of points in C

So with $q=7^2$ and the curve defined by $x^8 + y^8 = z^8$, we get $g=21$ and $n = q + 1 + 2g\sqrt{q}$. This example is in some sense maximal since it achieves the Hasse-Weil bound.

ECFFT Part 2

In ECFFT Part 1, the authors (Ben-Sasson, Carmon, Kopparty and Levit) described a way to generalize FFTs to arbitrary fields. In their following paper ECFFT Part 2, they generalize this even further and describe an end-to-end STARK-like proving system over arbitrary fields.

The recipe for STARK-like systems looks roughly like this

1. Start with a $n\times k$-table $T$ for which some constraint polynomial $C$ vanishes on every row.
2. Interpolate the columns on a domain $H$ to get polynomials $f_1(x),\dots,f_k(x)$.
3. The polynomial $C(f_1(x),\dots,f_k(x))$ vanishes on $H$, so we can its quotient with $Z_H(x)$, the vanishing polynomial over $H$.
4. Use polynomial commitments to succinctly prove that the quotient polynomial is computed correctly.

For fields with high $2$-adicity, step 2 can be performed efficiently using FFTs. For arbitrary fields, one can use the ECFFT algorithm where the domain $H$ corresponds to a subgroup of an elliptic curve over the field.

The constraint polynomial $C$ involves not only the column polynomials $f_i(x)$ but also their shifts. When $H$ is a multiplicative subgroup of the field, these can simply be written $f_i(gx)$ where $g$ is a generator of $H$.

When $H$ is a subgroup of an elliptic curve, the polynomials are seen as elements of the Riemann-Roch space $\L(D)$ with $D=\sum_{P\in H} P$. Then for an element $f \in \L(D)$, its shifted version is $P \mapsto f(G+P)$ where $G$ is a generator of $H$. Simplifying a lot, the proving system then works by replacing Reed-Solomon codes with algebraic geometry codes over this Riemann-Roch space and using an adapted version of FRI.

Reverse Multiplication Friendly Embedding (RMFE)

RMFEs, introduced in this paper, give a way to go between vectors over a small field to elements of an extension field. Namely, a $(n,m)$-RMFE is a pair of linear maps $\phi: \F_q^n \to \F_{q^m}$, $\psi: \F_{q^m} \to \F_q^n$ such that for all $x,y \in \F_q^n$,

$$ x \circ y = \psi(\phi(x)\cdot \phi(y)). $$

These can be used for SNARKs to transfer an instance over a small field $\F_q$ which is, e.g., too small for soundness or doesn’t have high $2$-adicity, to an instance over a larger extension field. When $q=2$, this produces SNARKs over boolean circuits (see these two papers).

Let $C$ be a curve over $\F_q$ of genus $g$, with $G$, $P_1,\dots,P_n$ and $ev$ like in our discussion of algebraic geometry code. Further assume that the dimension if the code is $n$, i.e., $ev$ is surjective. By Riemann-Roch, this happens for example when $\deg G = k + 2g - 1$. Finally, let $R$ be a point of $C$ over the extension field $F_{q^m}$, with $m > 2\deg G$. Then a $(n, m)$-RMFE can be constructed as follows.

• Let $W \subseteq \L(G)$ be a subspace such that $\left.ev\right|_W$ is an isomorphism between $W$ and $\F_q^n$.
• Let $\phi: ev(W)=\F_q^n \to \F_{q^m}$ be the function given by evaluation at $R$.
• We can construct an inverse $\psi: \F_{q^m} \to \F_q^n$ such that $(\phi, \psi)$ form a RMFE.