0.3 Elliptic Curve Cryptography

To create a decentralized ledger, we need a way for users to authenticate their transactions without relying on a central authority. This is where Elliptic Curve Cryptography (ECC) comes in.

Elliptic Curve Cryptography is a form of asymmetric cryptography that provides the same security as traditional methods like RSA but with much smaller key sizes. This efficiency makes it well-suited for use in blockchain and cryptocurrencies.

ECC is based on mathematical structures called elliptic curves, which follow an equation of the form:

$$y^2 = x^3+a\cdot x+b\ \ (\text{mod}\ p)$$

When we consider this equation in the domain of finite fields of the form Z/pZ where p is a prime number, the set of solutions forms a group, where addition is defined as the operation of adding points on the curve according to specific rules.

In ECC, addition of two points P and Q on the elliptic curve is defined geometrically:

• If P≠Q, draw a line through P and Q. This line will intersect the curve at a third point R. The reflection of R over the x-axis gives the sum P+Q.

• If P=Q, draw the tangent line at P. This line intersects the curve at a new point, which is reflected to get 2P.

• If the line is vertical, the result is the identity element (point at infinity).

A key operation in ECC is scalar multiplication, where a point P is added to itself repeatedly:

$$k\cdot P = P + P+...+P \ \ \text{ (}k\text{ times)}$$

These curves sometimes have unique properties that make cryptographic operations secure. One of the fundamental concepts behind ECC is the Elliptic Curve Discrete Logarithm Problem (ECDLP).

The idea is the following. Let's say we chose the elliptic curve parameters so the group of points on the curve has a cyclic sub-group of order q, a high prime, with generator G.

If someone takes a random scalar in [0, q-1] uniformly, and computes:

$$A=a\cdot G$$

Then the ECDLP is said to be "hard" if it is difficult to find $a$ given any $A$ in a short amount of time. Basically the only solution would have to be to check every possible $a$. Although it remains "easy" to compute $A$ from . In fact, parameters of ECC curves are also chosen to make computing a multiplication operation as fast as possible.

This is exactly how an asymmetric key pair is generated:

• Generate a random scalar $a\in [1, q-1]$

• Compute $A=a\cdot G$

$a$ is the private key, and $A$ the public key. On the chain, you are identified as A. You can broadcast your public key so other users can encrypt messages using $A$ that only you can decrypt. Let's see how this work in practice:

Encryption

$B$ wants to send a message to $A$. The message is encoded as a single field element: $m \in [0, p-1]$.

1. $B$ generate a random $r\in [1, q-1]$. It should be new and never be used again.

2. $B$ computes from $r$ a "nonce" group element: $N= r\cdot G$.

3. $B$ then generates a view key group element: $E= r\cdot A$.

4. $B$ hashes the view key to get a field element: $h= \text{hash}(E) \in [0, p-1]$.

5. $B$ calculates the cipher text: $c= m+h$.

$(c, N)$ is the encrypted message that can be shared with $A$ through an insecure channel.

Decryption

$A$ receives $(c, N)$, and recovers the original message $m$ following those steps;

1. $A$ computes $a\cdot N$, which is the view key group element $E$ because: $a\cdot N = a\cdot(r\cdot G) = (ar)\cdot G = (ra)\cdot G = r\cdot(a\cdot G) = r\cdot A=E$.

2. $A$ hashes the view key to get back the field element: $h= \text{hash}(E)$.

3. $A$ computes the plain text message: $m= c-h$.

Let's see in next chapter how your private key k allows you to authenticate the transaction you want to broadcast to the network to spend your coins.