2.6 Supersingular and ordinary elliptic curves

Supersingular and ordinary elliptic curves are two distinct classes of curves with unique properties. These curves play crucial roles in elliptic curve cryptography, offering different advantages and challenges in various applications.

Understanding the differences between supersingular and ordinary curves is essential for cryptographers and mathematicians. From endomorphism rings to isogeny structures, these curves exhibit distinct characteristics that impact their use in cryptographic protocols and mathematical research.

Supersingular elliptic curves

• Supersingular elliptic curves are a special class of elliptic curves with unique properties that distinguish them from ordinary elliptic curves
• These curves have been extensively studied in the context of elliptic curve cryptography due to their efficient computation and potential for constructing secure cryptographic protocols
• Understanding the characteristics and behavior of supersingular curves is crucial for their effective application in cryptography and other areas of mathematics

Definition of supersingularity

Top images from around the web for Definition of supersingularity

• 

  Category:Elliptic curves - Wikimedia Commons View original

  Is this image relevant?

• 

  Is the real locus of an elliptic curve the intersection of a torus with a plane? - Mathematics ... View original

  Is this image relevant?

• 

  A simple Elliptic Curve View original

  Is this image relevant?

• 

  Category:Elliptic curves - Wikimedia Commons View original

  Is this image relevant?

• 

  Is the real locus of an elliptic curve the intersection of a torus with a plane? - Mathematics ... View original

  Is this image relevant?

1 of 3

Top images from around the web for Definition of supersingularity

• 

  Category:Elliptic curves - Wikimedia Commons View original

  Is this image relevant?

• 

  Is the real locus of an elliptic curve the intersection of a torus with a plane? - Mathematics ... View original

  Is this image relevant?

• 

  A simple Elliptic Curve View original

  Is this image relevant?

• 

  Category:Elliptic curves - Wikimedia Commons View original

  Is this image relevant?

• 

  Is the real locus of an elliptic curve the intersection of a torus with a plane? - Mathematics ... View original

  Is this image relevant?

1 of 3

• An elliptic curve $E$ defined over a field $k$ of characteristic $p > 0$ is called supersingular if its $p$-torsion subgroup $E[p]$ is trivial
  • In other words, the group of points on $E$ annihilated by multiplication by $p$ is the identity element $\mathcal{O}$
• Equivalently, $E$ is supersingular if and only if the trace of the Frobenius endomorphism of $E$ is divisible by $p$
• Supersingularity is a geometric property of the curve that remains invariant under isomorphisms and extensions of the base field
• Examples of supersingular curves include the curve $y^2 = x^3 - x$ over $\mathbb{F}_p$ for $p \equiv 3 \pmod{4}$ and the curve $y^2 = x^3 + 1$ over $\mathbb{F}_p$ for $p \equiv 2 \pmod{3}$

Endomorphism rings of supersingular curves

• The endomorphism ring of a supersingular elliptic curve $E$ over a field $k$ is a maximal order in a quaternion algebra over $\mathbb{Q}$
  • A quaternion algebra is a 4-dimensional central simple algebra over a field
• The endomorphism ring of a supersingular curve is always non-commutative, unlike the case for ordinary curves
• The structure of the endomorphism ring provides insights into the isogeny graph of the curve and its potential for use in cryptography
• For example, the supersingular curve $y^2 = x^3 + x$ over $\mathbb{F}_p$ for $p \equiv 3 \pmod{4}$ has endomorphism ring isomorphic to the maximal order in the quaternion algebra ramified at $p$ and $\infty$

Isogenies of supersingular curves

• Isogenies are rational maps between elliptic curves that preserve the group structure
• For supersingular curves, the isogeny graph is a regular graph with a high degree of connectivity
  • This property is exploited in the construction of cryptographic protocols based on supersingular isogeny problems
• The isogeny graph of supersingular curves over a finite field $\mathbb{F}_{p^2}$ is known as the supersingular isogeny graph
• Isogenies of supersingular curves can be efficiently computed using Vélu's formulas, which provide explicit expressions for the coefficients of the codomain curve
• Examples of isogenies include the multiplication-by-$m$ map $[m] : E \to E$ and the Frobenius endomorphism $\pi : E \to E$ defined by $(x, y) \mapsto (x^p, y^p)$

Supersingular curves over finite fields

• Supersingular curves over finite fields have a rich structure and are of particular interest in cryptography
• Over a finite field $\mathbb{F}_q$ of characteristic $p$, there are approximately $\lfloor q/12 \rfloor$ isomorphism classes of supersingular curves
  • This is significantly fewer than the number of isomorphism classes of ordinary curves over the same field
• The supersingular isogeny graph over $\mathbb{F}_{p^2}$ is a $(p+1)$-regular graph, meaning that each vertex (curve) has exactly $p+1$ outgoing edges (isogenies)
• Supersingular curves over finite fields have been used to construct cryptographic protocols such as the supersingular isogeny Diffie-Hellman key exchange (SIDH) and the supersingular isogeny hash function (SIH)

Cryptographic applications of supersingular curves

• Supersingular curves have found numerous applications in elliptic curve cryptography due to their unique properties and efficient computation
• The supersingular isogeny Diffie-Hellman key exchange (SIDH) is a post-quantum key exchange protocol based on the difficulty of finding isogenies between supersingular curves
  • SIDH offers small key sizes and efficient computation compared to other post-quantum candidates
• The supersingular isogeny hash function (SIH) is a cryptographic hash function that maps binary strings to supersingular elliptic curves
  • SIH is collision-resistant and can be used for various cryptographic purposes, such as digital signatures and password hashing
• Supersingular curves have also been used in the construction of zero-knowledge proofs, identity-based encryption schemes, and other cryptographic primitives
• The security of cryptographic protocols based on supersingular curves relies on the hardness of problems such as the supersingular isogeny problem and the supersingular computational Diffie-Hellman problem

Ordinary elliptic curves

• Ordinary elliptic curves are the most common type of elliptic curves and have been extensively studied in mathematics and cryptography
• Unlike supersingular curves, ordinary curves have a commutative endomorphism ring and a different structure of the isogeny graph
• Understanding the properties and behavior of ordinary curves is essential for their effective use in cryptographic applications and theoretical investigations

Definition of ordinary curves

• An elliptic curve $E$ defined over a field $k$ of characteristic $p > 0$ is called ordinary if it is not supersingular
  • In other words, the $p$-torsion subgroup $E[p]$ is not trivial, and the trace of the Frobenius endomorphism is not divisible by $p$
• Ordinary curves constitute the majority of elliptic curves over a given field, with supersingular curves being a special case
• The property of being ordinary is preserved under isomorphisms and extensions of the base field
• Examples of ordinary curves include the curve $y^2 = x^3 - x$ over $\mathbb{F}_p$ for $p \equiv 1 \pmod{4}$ and the curve $y^2 = x^3 + ax + b$ over $\mathbb{Q}$ for most choices of $a$ and $b$

Endomorphism rings of ordinary curves

• The endomorphism ring of an ordinary elliptic curve $E$ over a field $k$ is an order in an imaginary quadratic field
  • An imaginary quadratic field is a number field of the form $\mathbb{Q}(\sqrt{-d})$, where $d$ is a positive square-free integer
• The endomorphism ring of an ordinary curve is always commutative, unlike the case for supersingular curves
• The structure of the endomorphism ring provides information about the isogenies and complex multiplication properties of the curve
• For example, the ordinary curve $y^2 = x^3 - x$ over $\mathbb{F}_p$ for $p \equiv 1 \pmod{4}$ has endomorphism ring isomorphic to the ring of integers of the imaginary quadratic field $\mathbb{Q}(\sqrt{-1})$

Isogenies of ordinary curves

• Isogenies between ordinary elliptic curves have a different structure compared to those of supersingular curves
• The isogeny graph of ordinary curves is not as highly connected as the supersingular isogeny graph, and the degrees of isogenies are more restricted
• Computing isogenies between ordinary curves is generally more challenging than in the supersingular case, as the formulas for isogenies are more complex
• Isogenies of ordinary curves have been used in the construction of cryptographic protocols, such as the CRS (Charles-Goren-Lauter) hash function and the CSIDH (Commutative Supersingular Isogeny Diffie-Hellman) key exchange

Ordinary curves over finite fields

• Ordinary curves over finite fields have been widely studied and applied in elliptic curve cryptography
• Over a finite field $\mathbb{F}_q$ of characteristic $p$, the number of isomorphism classes of ordinary curves is approximately $q$, which is significantly larger than the number of supersingular curves
• Ordinary curves over finite fields have a rich theory of complex multiplication, which relates the endomorphism ring of the curve to the ring of integers of an imaginary quadratic field
• The complex multiplication method can be used to construct ordinary curves with desired properties, such as a specific group order or endomorphism ring

Cryptographic applications of ordinary curves

• Ordinary elliptic curves have been extensively used in the design and implementation of various cryptographic protocols
• The most common use of ordinary curves is in the Elliptic Curve Diffie-Hellman (ECDH) key exchange and the Elliptic Curve Digital Signature Algorithm (ECDSA)
  • These protocols rely on the hardness of the elliptic curve discrete logarithm problem (ECDLP) for their security
• Ordinary curves have also been used in the construction of pairing-based cryptography, where bilinear pairings on elliptic curves are used to build advanced cryptographic primitives
  • Examples include the Boneh-Franklin identity-based encryption scheme and the Boneh-Lynn-Shacham (BLS) signature scheme
• The choice of ordinary curves for cryptographic applications is guided by security considerations, efficiency requirements, and standards set by organizations such as NIST (National Institute of Standards and Technology)
• Some widely used ordinary curves in cryptography include secp256k1 (used in Bitcoin), NIST P-256, and Curve25519

Supersingular vs ordinary curves

• Supersingular and ordinary elliptic curves have distinct properties that make them suitable for different cryptographic applications
• Understanding the differences between these two classes of curves is crucial for selecting the appropriate type of curve for a given cryptographic protocol or mathematical investigation
• The comparison of supersingular and ordinary curves involves aspects such as their endomorphism rings, isogeny structures, and performance in cryptographic implementations

Differences in endomorphism rings

• The endomorphism rings of supersingular and ordinary curves have fundamentally different structures
• Supersingular curves have non-commutative endomorphism rings that are maximal orders in quaternion algebras over $\mathbb{Q}$
  • This non-commutativity leads to a rich and complex structure of the endomorphism ring
• Ordinary curves, on the other hand, have commutative endomorphism rings that are orders in imaginary quadratic fields
  • The commutativity of the endomorphism ring allows for a simpler and more well-understood structure
• The differences in endomorphism rings have implications for the isogeny graphs and the potential for constructing cryptographic protocols based on isogeny problems

Differences in isogeny structures

• The isogeny graphs of supersingular and ordinary curves exhibit distinct characteristics that impact their use in cryptography
• Supersingular curves have a highly connected isogeny graph, with each curve having a large number of outgoing isogenies (approximately $p+1$ over $\mathbb{F}_{p^2}$)
  • This dense connectivity is exploited in the construction of cryptographic protocols like SIDH and SIH
• Ordinary curves have a sparser isogeny graph, with fewer isogenies between curves and more restricted degrees of isogenies
  • The structure of the isogeny graph of ordinary curves is more complex and less well-understood compared to the supersingular case
• The differences in isogeny structures affect the design and security analysis of isogeny-based cryptographic protocols

Comparative performance in cryptography

• The performance of supersingular and ordinary curves in cryptographic implementations depends on various factors, such as the specific protocol, the chosen parameters, and the implementation details
• Supersingular curves often allow for more efficient computation of certain operations, such as point multiplication and isogeny evaluation
  • This efficiency is due to the special structure of supersingular curves and the availability of optimized algorithms for these operations
• Ordinary curves, while generally slower in terms of computation, benefit from a wider range of available curves and more mature implementation techniques
  • The use of ordinary curves in cryptography has a longer history, and there are well-established standards and best practices for their implementation
• The comparative performance of supersingular and ordinary curves in cryptography is an active area of research, and the choice between the two depends on the specific requirements and constraints of the application

Comparative security in cryptography

• The security of cryptographic protocols based on supersingular and ordinary curves relies on different hardness assumptions and is subject to different types of attacks
• Supersingular curves are often used in the construction of post-quantum cryptographic protocols, as they are believed to be resistant to attacks by quantum computers
  • The security of supersingular isogeny-based protocols, such as SIDH, relies on the hardness of the supersingular isogeny problem and its variants
• Ordinary curves, when used in classical elliptic curve cryptography, rely on the hardness of the elliptic curve discrete logarithm problem (ECDLP)
  • The security of ordinary curve-based protocols, such as ECDH and ECDSA, is well-studied, and there are established guidelines for selecting secure curve parameters
• The comparative security of supersingular and ordinary curves is an ongoing research topic, and the choice between the two depends on the specific security requirements and the assumed capabilities of potential adversaries
• Factors such as key sizes, available attacks, and the impact of future cryptanalytic advances should be considered when comparing the security of supersingular and ordinary curve-based cryptography