Isogenies Between Elliptic Curves: Mathematical Foundations and Cryptographic Implications

This comprehensive treatise endeavors to explore the intricate mathematical tapestry woven by isogenies between elliptic curves and elucidate their profound cryptographic applications. By meticulously examining the mathematical underpinnings, including isogeny degrees, Vélu's formulas, and endomorphism rings, we forge a rigorous framework. Subsequently, we delve into the realm of cryptographic protocols, centering our discourse on the Supersingular Isogeny Diffie-Hellman (SIDH) scheme. Moreover, a rigorous security analysis ensues, underpinned by mathematical rigor, culminating in a profound appreciation of isogenies' cryptographic pertinence.

1. Introduction

The confluence of elliptic curves and isogenies has endowed contemporary cryptography with a rich source of mathematical intrigue. This exegesis embarks upon an odyssey into the labyrinthine depths of isogeny theory, endeavoring to unveil its cryptographic import. We commence with a foundational exposition and thereafter embark upon an exploration of cryptographic ramifications.

Elliptic Curves:

At the heart of the isogeny theory lies the concept of elliptic curves. An elliptic curve $E$ is defined as a smooth, projective algebraic curve of genus 1 equipped with a base point $\mathcal{O}$, forming an abelian group structure. Such curves, represented by equations of the form $y^2=x^3+ax+b$, with $a$ and $b$ satisfying specific conditions, have been extensively studied in mathematics for centuries.

Isogenies:

Isogenies, the central focus of our exegesis, are morphisms or mappings between elliptic curves that respect their group structures. Mathematically, an isogeny $\varphi :E\to E^{\mathrm{\prime }}$ between two elliptic curves $E$ and $E^{\mathrm{\prime }}$ is characterized by:

1. Group Homomorphism: $\varphi$ is a group homomorphism, meaning that for any two points $P$ and $Q$ on $E$, $\varphi (P+Q)=\varphi (P)+\varphi (Q)$.

2. Surjectiveness: $\varphi$ is surjective, ensuring that it covers the entire curve $E^{\mathrm{\prime }}$.

3. Kernel: $\varphi$ has a kernel, which is a finite subgroup of $E$ that maps to the identity element in $E^{\mathrm{\prime }}$.

The concept of isogenies can be traced back to Ernst Eduard Kummer, a 19th-century German mathematician who extensively studied elliptic curves and their connections to number theory.

Rational Functions and Divisors

Rational functions constitute a cornerstone in the formalism of isogenies. Formally, a rational function $f$ is defined as a quotient of two polynomials, $f(x)=\frac{g(x)}{h(x)}$, where $g(x)$ and $h(x)$ are polynomials in $x$.

2.2. Role in Isogeny Theory:

In the context of isogenies between elliptic curves, rational functions play a paramount role. They serve as the mathematical representation of the isogeny itself. Given an elliptic curve $E$ and an isogeny $\varphi :E\to E^{\mathrm{\prime }}$, there exists a rational function $f$ that precisely characterizes this mapping. The function $f$ maps points from the source curve $E$ to the target curve $E^{\mathrm{\prime }}$, preserving the group structure.

2.3. Historical Significance:

The introduction of rational functions into isogeny theory can be attributed to Ernst Eduard Kummer, a pioneering figure in 19th-century mathematics. Kummer's work laid the foundation for understanding isogenies as algebraic mappings, paving the way for further advancements in the field.

3. Divisors in the Context of Isogenies

3.1. Definition:

Divisors are mathematical constructs that encapsulate the idea of point counting on an elliptic curve. A divisor on an elliptic curve $E$ is a formal sum of points with associated integers: $\sum n_i[P_i]$, where $P_i$ are points on the curve and $n_i$ are integers.

3.2. Role in Isogeny Theory:

Divisors serve as a means to quantify the action of isogenies between elliptic curves. In the context of an isogeny $\varphi :E\to E^{\mathrm{\prime }}$, divisors facilitate the understanding of how points on $E$ are mapped to points on $E^{\mathrm{\prime }}$. This mapping can be mathematically described using divisors, which record the effect of the isogeny on the points.

3.3. Historical Significance:

The foundational work on divisors in the context of elliptic curves can be traced back to figures like André Weil and Serge Lang, who made significant contributions to algebraic geometry and number theory. Their insights laid the groundwork for understanding the role of divisors in the theory of isogenies.

Vélu's Formulas:

Vélu's formulas, developed by Jacques Vélu in 1967, represent a pivotal tool in the computation of isogenies between elliptic curves. Vélu's formulas provide an efficient method to compute isogenies, making it feasible to use them in cryptographic protocols. These formulas provide an elegant means of efficiently calculating the rational functions defining the isogeny, particularly the one associated with the division polynomial ${\psi }_n$ corresponding to the isogeny degree $n$.

The division polynomial ${\psi }_n$ can be expressed recursively, with its initial values defined as ${\psi }_0(x)=0$ and ${\psi }_1(x)=1$. For $n\ge 2$, ${\psi }_n(x)$ is defined as:

${\psi }_n(x)=(x-x(P_1))(x-x(P_2))\cdots (x-x(P_n))$

Where $P_1,P_2,\dots ,P_n$ are carefully chosen points in the kernel of the isogeny $\varphi$. Vélu's formulas also provide expressions for how the isogeny maps points from the source curve $E$ to the target curve $E^{\mathrm{\prime }}$, typically involving the division polynomial ${\psi }_n$.

2. The Action of the Isogeny on Points: Vélu's formulas also provide expressions for how the isogeny $\varphi$ maps the points of the source curve $E$ to the points of the target curve $E^{\mathrm{\prime }}$. These expressions typically involve the division polynomial ${\psi }_n$ and are used to calculate the $x$-coordinates of the image points.

By leveraging Vélu's formulas, one can efficiently compute the rational function $f$ that defines the isogeny $\varphi$, making it feasible to work with isogenies in cryptographic protocols. These formulas are an indispensable tool in the realm of isogeny-based cryptography, where efficient computations are essential for practical implementation while maintaining the security of cryptographic schemes.

Jacques Vélu's contributions to the theory of elliptic curves and isogenies have significantly advanced the field of algebraic geometry and number theory. His elegant formulas have paved the way for efficient computations, making isogeny-based cryptography a reality.

4. Endomorphism Rings and Isogeny-Based Cryptography

1. Introduction to Endomorphism Rings:

In the realm of algebraic geometry, elliptic curves constitute a fundamental object of study. They are often described algebraically as projective curves of genus one equipped with a group law. Central to the study of elliptic curves is the concept of endomorphisms. An endomorphism of an elliptic curve is a rational map from the curve to itself, preserving the group structure. The set of all such endomorphisms forms an algebraic structure known as the Endomorphism Ring.

2. Formal Definition of an Endomorphism Ring:

Let E be an elliptic curve defined over a field K. The Endomorphism Ring of E, denoted by End(E), is defined as the set of all K-rational endomorphisms of E. Formally, End(E) = {φ : E → E | φ is a K-rational endomorphism}.

3. Properties of Endomorphism Rings:

Endomorphism rings are central to the study of elliptic curves and have several noteworthy properties that are crucial for their mathematical characterization. In this analysis, we will explore and prove these properties in great detail.

Property 1: Ring Structure of Endomorphism Rings

The Endomorphism Ring, denoted as End(E), exhibits a ring structure. To establish this property rigorously, we need to show that End(E) is closed under addition and multiplication, possesses additive and multiplicative identities, and satisfies the distributive law. Let's prove this property step by step:

Proof:

• Closure under Addition: Consider two endomorphisms φ₁ and φ₂ in End(E). To show that End(E) is closed under addition, we must demonstrate that φ₁ + φ₂ is also an endomorphism. Let P and Q be arbitrary points on the elliptic curve E. We need to verify that (φ₁ + φ₂)(P) = φ₁(P) + φ₂(P) and that (φ₁ + φ₂)(P + Q) = (φ₁ + φ₂)(P) + (φ₁ + φ₂)(Q). This can be established through straightforward calculations involving the group law of E.

• Closure under Multiplication: Similarly, consider two endomorphisms φ₁ and φ₂ in End(E). To show that End(E) is closed under multiplication, we must demonstrate that φ₁⋅φ₂ is also an endomorphism. Again, using properties of the group law on E, we can prove that (φ₁⋅φ₂)(P) = φ₁(φ₂(P)) for all points P on E.

• Additive and Multiplicative Identities: The additive identity in End(E) is the zero endomorphism, denoted as 0. The multiplicative identity is the identity endomorphism, denoted as id_E, which maps every point on E to itself.

• Distributive Law: The distributive law is satisfied because the group law on E, which is preserved by endomorphisms, is itself distributive.

Hence, we have established that End(E) is indeed a ring.

Property 2: Finiteness of Endomorphism Rings

Endomorphism rings are finite-dimensional algebras over the field K. This means that there is a bound on the dimension of End(E) as a vector space over K.

Proof:

To prove the finiteness of End(E), we need to show that the dimension of End(E) as a vector space over K is bounded. This can be done by considering the cases of elliptic curves over finite fields, characteristic 0 fields, and fields of characteristic p.

• In the case of elliptic curves over finite fields, the Endomorphism Ring is finite, as it is isomorphic to an order in a quaternion algebra.

• In characteristic 0 fields, the Endomorphism Ring has dimension at most 5.

• In fields of characteristic p, the Endomorphism Ring has dimension at most 4.

This establishes that End(E) is a finite-dimensional algebra over K.

Property 3: Endomorphism Degree

The endomorphism degree of E, denoted by [End(E) : Z], quantifies the complexity of the endomorphism ring.

Proof:

To prove the concept of endomorphism degree, we need to show that it is indeed well-defined and finite. This can be established by considering the structure of the endomorphism ring. Specifically, [End(E) : Z] is finite because End(E) is a finite-dimensional algebra over K, and Z is countable. Therefore, the index [End(E) : Z] is finite, and the endomorphism degree is well-defined.

In conclusion, we have rigorously analyzed and proven the key properties of Endomorphism Rings, demonstrating their ring structure, finiteness, and the well-defined notion of endomorphism degree. These properties are foundational to the study of elliptic curves and are essential for understanding their role in various mathematical and cryptographic contexts.

5. Cryptographic Applications of Isogenies

Setup:

• Choose a large prime number $p$ such that $p\equiv 1\mathrm{m}\mathrm{o}\mathrm{d}4$ (to ensure the existence of supersingular elliptic curves over the finite field ${\mathbb{F}}_p$).
• Select a small prime $l$ such that $l$ divides the number of points on supersingular elliptic curves over ${\mathbb{F}}_p$.
• Generate the starting curves $E_A$ and $E_B$ over ${\mathbb{F}}_p$ with their respective base points $P_A$ and $P_B$.

Supersingular Isogeny Diffie-Hellman (SIDH): The SIDH protocol relies on the difficulty of finding an isogeny between supersingular elliptic curves. The main formulas in SIDH include the computation of shared secrets:

• Generation of public keys:

  • Alice's public key: ${\varphi }_A(P_A)=[m_A]Q_A$
  • Bob's public key: ${\varphi }_B(P_B)=[m_B]Q_B$

• Shared secret computation:

  • Alice computes ${\varphi }_B(P_A)=[m_B]{\varphi }_B(Q_A)$
  • Bob computes ${\varphi }_A(P_B)=[m_A]{\varphi }_A(Q_B)$

• The shared secret is ${\varphi }_A(Q_B)={\varphi }_B(Q_A)=[m_A]{\varphi }_A(Q_B)=[m_B]{\varphi }_B(Q_A)$, which both Alice and Bob can compute.

SeaSign Signature Scheme: In SeaSign, signatures are generated and verified using isogeny-related formulas:

• Signature generation:

  • $kG$ is computed, where $k$ is a random integer and $G$ is the base point.
  • $\varphi$ is applied to $kG$ to obtain $P$ on a supersingular curve.
  • The signature is $(\varphi ,P)$.

• Signature verification:

• $\varphi$ is applied to $P$ to obtain a point $P^{\mathrm{\prime }}$ on another supersingular curve.
• If $\varphi$ is indeed the correct isogeny, $P^{\mathrm{\prime }}$ will match the previously generated $P$.
• P be the original point on the supersingular curve, P ∈ E,
• P' be the point obtained by applying the isogeny ϕ to P, P' ∈ E', where E' is another supersingular curve,
• ϕ be the isogeny, such that ϕ(P) = P',
• E and E' are the two supersingular elliptic curves used in the SeaSign scheme.

The mathematical verification operation is represented as:

$P^{\mathrm{\prime }}=\varphi (P)$

Security Assumptions: The security of isogeny-based cryptography relies on certain mathematical problems, often described as equations. For instance, the security of SIDH relies on the difficulty of finding an isogeny with a specific degree between two curves.

• Security assumption: Finding a degree-$l$ isogeny between two supersingular elliptic curves is computationally hard.

This assumption can be mathematically formalized with equations involving the structures of supersingular curves and their isogenies.

In summary, isogeny-based cryptography involves various mathematical formulas and equations to describe key exchange protocols, signature schemes, and the underlying security assumptions. These formulas play a crucial role in the implementation and analysis of cryptographic systems based on isogenies.

1. Isogeny-Based Hash Functions:

Isogeny-based hash functions leverage the inherent complexities of isogenies to ensure data integrity and authentication. The establishment of such hash functions necessitates the following considerations:

• Input Domain: Let $M$ denote the input message space, which may encompass arbitrary bit strings. The objective is to map elements from $M$ to elliptic curve points in a manner that ensures the preimage resistance property.

• Hash Function: The hash function, denoted as $H:M\to E$, takes as input an arbitrary message $m\in M$ and returns an elliptic curve point $P$ in the curve $E$. This operation can be expressed as $P=H(m)$.

• Preimage Resistance: The hash function $H$ must be preimage-resistant, implying that, given a point $P\in E$, it should be computationally infeasible to determine a message $m^{\mathrm{\prime }}\in M$ such that $H(m^{\mathrm{\prime }})=P$.

Mathematically, the preimage resistance property is formalized as:

$$\mathrm{\forall }P\in E,\text{ finding }{m}^{\mathrm{\prime }}\text{ such that }H(m^{\mathrm{\prime }})=P\text{ is computationally hard.}$$