Elliptic Curves

Foundations of Modern Cryptography

Elliptic curves are fundamental objects in both mathematics and cryptography. They are defined by equations of the form:

$y^2 = x^3 + ax + b$

where $a$ and $b$ are constants that define the specific curve. This equation describes a smooth, continuous curve with no sharp points or cusps, provided the curve is non-singular. The condition for non-singularity is that the discriminant $A=-16(4a^3+27b^2)$ is not zero. Below are examples of such elliptic curves.

While these curves are helpful for visualisation, cryptographers use elliptic curves defined over finite fields. In these fields, calculations are performed modulo a prime number $p$, resulting in a finite set of points. This makes computations efficient and secure, but the curves appear as discrete sets of points rather than continuous lines.

One of the most intriguing properties of elliptic curves is their group structure: you can “add” points on the curve to get another point on the curve, forming an abelian group. To add two points $P$ and $Q$ on the curve:

1. Draw a straight line through $P$ and $Q$.
2. The line intersects the curve at a third point, $R$.
3. Reflect $R$ over the x-axis to obtain the point $P+Q$.

When $P=Q$, the line is the tangent to the curve at $P$, and the same process applies.

In the demonstration above, we use elliptic curves over the real numbers for clarity, illustrating how point addition works visually.

Fields

Elliptic curves can be defined over different types of fields. The most commonly used fields in cryptography are:

• Finite Fields: Denoted $\mathbb{F}_p$​ for a prime $p$, these fields consist of the set $\{0,1,2,…,p−1\}$, with addition and multiplication performed modulo $p$. Finite fields provide a discrete set of points and are essential for practical cryptographic applications due to their computational efficiency.

• Fields of Real Numbers: While elliptic curves over the real numbers $\mathbb{R}$ are useful for visualisation and theoretical understanding, they are not used in cryptographic implementations because real numbers cannot be represented exactly in a computer and computations over $\mathbb{R}$ are inefficient.

Relevance in Cryptography

Elliptic curves play a pivotal role in modern cryptography, leading to a field known as Elliptic Curve Cryptography (ECC). ECC enables the creation of cryptographic keys that are significantly smaller than those required by traditional systems like RSA, while providing equivalent security levels. This efficiency makes ECC particularly valuable in environments with limited computational resources, such as mobile devices and embedded systems.

The security of ECC is based on the difficulty of the Elliptic Curve Discrete Logarithm Problem (ECDLP). Given a point PP on an elliptic curve and a scalar multiple $Q=kP$ (where $k$ is an integer and $P$ is a point on the curve), it is computationally infeasible to determine $k$ from $P$ and $Q$. This one-way function underpins the security of ECC, making it resistant to attacks that attempt to derive private keys from public keys.

In cryptographic systems:

• Private Key: A randomly selected integer $k$ within a specified range.
• Public Key: The point $Q=kP$, where $P$ is a publicly known base point on the curve.

This simple operation forms the foundation for secure cryptographic schemes such as the Elliptic Curve Diffie-Hellman (ECDH) key exchange and the Elliptic Curve Digital Signature Algorithm (ECDSA).

This mechanism is also how cryptocurrency wallets function. Your private key is a scalar $k$, and your public key is the point $Q=kP$. When you send a transaction, you sign it with your private key, and others can verify the signature using your public key. Due to the hardness of the ECDLP, it’s practically impossible for someone to deduce your private key from your public key, ensuring the security of your transactions.

Chains of Curves and Curve Compositions

In advanced cryptographic systems, elliptic curves can be composed in what’s known as pairing-based cryptography. This involves using multiple elliptic curves where operations on one curve can be related to operations on another through a mathematical pairing function. This composition allows for more complex cryptographic protocols, such as zero-knowledge proofs and identity-based encryption.

For example, in certain cryptographic protocols, points on one curve can be mapped to elements in a finite field or another curve, enabling operations like proof aggregation and proof composition. This is essential in systems that require verifying multiple proofs efficiently.

In our system, we update our data structure with a user’s data and generate a proof that the update was performed correctly. We can then aggregate multiple such proofs and create a single, composite proof. When verified, this composite proof confirms that all the individual updates were executed correctly. This powerful technique allows us to scale our system to handle large amounts of data while maintaining high levels of security and efficiency.