🔢Elliptic Curves Unit 1 – Foundations of elliptic curves

Key Concepts and Definitions

• Elliptic curves are cubic equations of the form $y^2 = x^3 + ax + b$ where $a$ and $b$ are constants and the discriminant $\Delta = 4a^3 + 27b^2 \neq 0$
• The points on an elliptic curve form an abelian group under a specific operation called the group law
  • The group law involves adding points on the curve geometrically by drawing a line through them and finding the third point of intersection
• The identity element of the group is the point at infinity, denoted as $\mathcal{O}$
• Elliptic curves over finite fields $\mathbb{F}_q$ are of particular interest in cryptography due to their discrete logarithm problem being hard to solve
• The order of an elliptic curve $E(\mathbb{F}_q)$ is the number of points on the curve, including the point at infinity
• The Mordell-Weil theorem states that the group of rational points on an elliptic curve is finitely generated
• Elliptic curves are used in various cryptographic protocols such as Elliptic Curve Diffie-Hellman (ECDH) and Elliptic Curve Digital Signature Algorithm (ECDSA)

Historical Context and Development

• Elliptic curves were first studied in connection with the problem of computing the arc length of an ellipse by Giulio Fagnano in 1738
• Leonhard Euler further investigated the addition law on cubic curves in the 18th century, laying the groundwork for the group structure
• In the 19th century, Niels Henrik Abel and Carl Gustav Jacobi explored the double periodicity of elliptic functions, which are related to elliptic curves
• The Mordell-Weil theorem, proving the finite generation of rational points on elliptic curves, was conjectured by Louis Mordell in 1922 and proven by André Weil in 1928
• In the 1980s, the use of elliptic curves in cryptography was independently proposed by Neal Koblitz and Victor Miller
  • This led to the development of various elliptic curve cryptographic protocols (ECDH, ECDSA)
• The Birch and Swinnerton-Dyer conjecture, relating the rank of an elliptic curve to the behavior of its L-function, remains one of the most important open problems in number theory

Mathematical Foundations

• Elliptic curves are defined over a field $K$, typically the real numbers, complex numbers, or a finite field
• The Weierstrass equation of an elliptic curve is given by $y^2 + a_1xy + a_3y = x^3 + a_2x^2 + a_4x + a_6$, where $a_1, a_2, a_3, a_4, a_6 \in K$
  • The simplified Weierstrass equation $y^2 = x^3 + ax + b$ is commonly used when the characteristic of $K$ is not 2 or 3
• The discriminant $\Delta = -16(4a^3 + 27b^2)$ must be nonzero for the curve to be smooth (no cusps or self-intersections)
• The j-invariant of an elliptic curve is given by $j = 1728 \frac{4a^3}{4a^3 + 27b^2}$ and characterizes isomorphism classes of elliptic curves over algebraically closed fields
• Elliptic curves are equipped with a group structure, where the group operation is defined geometrically using the chord-and-tangent method
• The Nagell-Lutz theorem provides a criterion for determining if a point on an elliptic curve has finite order

Geometric Properties

• Elliptic curves are nonsingular cubic curves, meaning they have no cusps or self-intersections
• The shape of an elliptic curve depends on the coefficients $a$ and $b$ in the Weierstrass equation
  • Different values of $a$ and $b$ can result in curves with varying numbers of connected components and real points
• Elliptic curves are symmetric about the x-axis, as for every point $(x, y)$ on the curve, there is also a point $(x, -y)$
• The group law on an elliptic curve has a geometric interpretation:
  • To add two points $P$ and $Q$, draw a line through them and find the third point of intersection $R$. The sum $P + Q$ is the reflection of $R$ about the x-axis
  • If $P = Q$, the line is the tangent line at $P$, and the sum $P + P = 2P$ is the reflection of the second point of intersection about the x-axis
• The point at infinity $\mathcal{O}$ serves as the identity element for the group law and is the third point of intersection for any vertical line
• Elliptic curves have a rich geometric structure, with concepts such as torsion points, isogenies, and complex multiplication

Algebraic Structure

• The set of points on an elliptic curve $E$, together with the point at infinity $\mathcal{O}$, forms an abelian group under the addition operation defined by the group law
  • The group $(E, +)$ satisfies the axioms of associativity, identity, inverses, and commutativity
• The torsion subgroup of $E$ consists of all points of finite order, i.e., points $P$ such that $nP = \mathcal{O}$ for some positive integer $n$
  • The torsion subgroup is always finite and can be classified using the Nagell-Lutz theorem and Mazur's theorem
• The rank of an elliptic curve is the number of independent points of infinite order in the group $E(\mathbb{Q})$ of rational points
  • The Mordell-Weil theorem states that the rank is always finite, but determining the rank is a difficult problem related to the Birch and Swinnerton-Dyer conjecture
• Elliptic curves over finite fields $\mathbb{F}_q$ have a finite number of points, and the group $E(\mathbb{F}_q)$ is always finite
  • The order of $E(\mathbb{F}_q)$ satisfies Hasse's theorem: $|q + 1 - \#E(\mathbb{F}_q)| \leq 2\sqrt{q}$
• Isogenies are algebraic mappings between elliptic curves that preserve the group structure and can be used to study the relationships between different curves

Group Law and Operations

• The group law on an elliptic curve $E$ is defined by the chord-and-tangent method:
  • To add points $P$ and $Q$, draw a line through them and find the third point of intersection $R$. The sum $P + Q$ is the reflection of $R$ about the x-axis
  • If $P = Q$, use the tangent line at $P$ instead, and the sum $P + P = 2P$ is the reflection of the second point of intersection about the x-axis
• The point at infinity $\mathcal{O}$ serves as the identity element: $P + \mathcal{O} = P$ for all points $P$ on the curve
• The inverse of a point $P = (x, y)$ is its reflection about the x-axis: $-P = (x, -y)$
  • This satisfies $P + (-P) = \mathcal{O}$ for all points $P$ on the curve
• The group law can be expressed algebraically using the coordinates of the points:
  • For points $P = (x_1, y_1)$ and $Q = (x_2, y_2)$ with $P \neq \pm Q$, the sum $P + Q = (x_3, y_3)$ is given by:
    • $x_3 = \lambda^2 - x_1 - x_2$
    • $y_3 = \lambda(x_1 - x_3) - y_1$
    • where $\lambda = \frac{y_2 - y_1}{x_2 - x_1}$ if $P \neq Q$, and $\lambda = \frac{3x_1^2 + a}{2y_1}$ if $P = Q$
• Scalar multiplication is the repeated addition of a point to itself: $nP = P + P + \cdots + P$ ($n$ times)
  • Efficient algorithms, such as the double-and-add method, are used to compute scalar multiples of points

Applications in Cryptography

• Elliptic curve cryptography (ECC) is based on the difficulty of the elliptic curve discrete logarithm problem (ECDLP):
  • Given points $P$ and $Q$ on an elliptic curve, find an integer $n$ such that $Q = nP$
• ECC offers the same level of security as other public-key cryptosystems (RSA, DSA) with smaller key sizes, making it more efficient and suitable for resource-constrained devices
• Elliptic Curve Diffie-Hellman (ECDH) is a key agreement protocol that allows two parties to establish a shared secret over an insecure channel
  • Alice and Bob agree on an elliptic curve $E$ and a base point $P$. They choose secret integers $a$ and $b$, compute $aP$ and $bP$, and exchange these values. The shared secret is $abP$
• Elliptic Curve Digital Signature Algorithm (ECDSA) is used for digital signatures and authentication
  • The signer chooses a secret key $d$ and computes the public key $Q = dP$. To sign a message $m$, the signer computes $r = x_1 \bmod n$ and $s = k^{-1}(H(m) + dr) \bmod n$, where $k$ is a random integer, $(x_1, y_1) = kP$, $H$ is a hash function, and $n$ is the order of $P$
  • The signature is the pair $(r, s)$, and verification involves checking that $r = x_2 \bmod n$, where $(x_2, y_2) = u_1P + u_2Q$, $u_1 = H(m)s^{-1} \bmod n$, and $u_2 = rs^{-1} \bmod n$
• Other ECC-based protocols include the Elliptic Curve Integrated Encryption Scheme (ECIES) and the Elliptic Curve Menezes-Qu-Vanstone (ECMQV) key agreement protocol

Advanced Topics and Open Problems

• The Birch and Swinnerton-Dyer conjecture relates the rank of an elliptic curve $E$ over $\mathbb{Q}$ to the behavior of its L-function $L(E, s)$ at $s = 1$
  • It states that the rank of $E(\mathbb{Q})$ is equal to the order of vanishing of $L(E, s)$ at $s = 1$, and the leading coefficient of the Taylor series of $L(E, s)$ at $s = 1$ is related to other arithmetic invariants of $E$
  • The conjecture has been proven for specific cases but remains open in general
• Elliptic curves with complex multiplication have additional structure and are of interest in number theory and cryptography
  • An elliptic curve $E$ has complex multiplication if its endomorphism ring $\text{End}(E)$ is larger than $\mathbb{Z}$
  • Curves with complex multiplication have applications in primality testing and the construction of cryptographically secure curves
• Hyperelliptic curves are generalizations of elliptic curves, defined by equations of the form $y^2 + h(x)y = f(x)$, where $h(x)$ and $f(x)$ are polynomials and the degree of $f(x)$ is greater than 4
  • Hyperelliptic curve cryptography offers potential advantages in terms of efficiency and security, but the mathematical theory is more complex than that of elliptic curves
• Pairings on elliptic curves, such as the Weil pairing and the Tate pairing, have applications in cryptography and can be used to construct identity-based encryption and signature schemes
  • Pairings map pairs of points on an elliptic curve to elements of a finite field and have properties that enable new cryptographic functionalities
• The study of elliptic curves over various fields and rings, such as p-adic fields and function fields, leads to deep connections with other areas of mathematics, including algebraic geometry, harmonic analysis, and representation theory