Elliptic Curve Cryptography

: used by Bitcoin and Ethereum to implement public key cryptography. Elliptic curve over a field where is a 256-bit prime.

ECDSA: Elliptic Curve Digital Signature Algorithm

Public key cryptography uses this method to calculate public keys which is a point on ECC curve.

  • = 512-bit public key
  • = 256-bit randomly generated private key
  • = base point on the curve
  • = prime number

Take a base point , add it (private key) times to make (public key).

Note: addition here means addition in elliptic curve and not addition in field of integers mod p.

Order of a base point is when keys generated using this point starts to form a cycle. Max number of points on the curve.

Thus, choosing a good base point is necessary in any public key generation curves.

secp256k1:

x = 0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798
y = 0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8
p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F

The order is:

N = FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141

Ethereum public keys are serialisation of 130 hex characters

04 + x-coord (64) + y-coord (64)

04 is prefixed as it is used to define uncompressed point on the ECC.

Ethereum addresses are hexadecimal numbers, identifiers derived from the last 20 bytes of the Keccak256 hash of the public key.

Why Discrete Logarithm?

ECC is significant because solving is trivial but obtaining from product is not.

can be obtained using Fast-Exponentiation algorithm but solving for requires computing discrete logarithms.

Security

Big-O Notation of discrete logarithm problem is .

Base point , is chosen to be closer to and thus is in the order of 256.

So, bits level of security is provided by curves like .

secp256k1 v/s secp256r1

is a Koblitz curve defined in a characteristic 2 finite field while is a prime field curve.

Not going into details as to what a characteristic 2 finite field is, we can specify as a pseudo-randomised curve and as completely random curve which can’t be solved using discrete logarithm problem yet.

Pairing Friendly Curves

Pairing-based cryptography is a new cryptographic primitive that has been developed in recent times, enabling new applications like short digital signatures that are aggregatable, identity-based cryptography, MPC, efficient polynomial commitments.

They have a favourable embedding degree, and a large prime-order subgroup.

BLS12-381

Most of these notes are taken from this amazing post by Ben

This was first introduced by Sean Bowe from ZCash in 2017 and has been used in various things from then. Now for the naming,

  • BLS stands for Barreto, Lynn, Scott.
  • 12 stands for embedding degree of the curve
  • 381 stands for the order of the prime used for the field , i.e. number of bits used to represent coordinates on the curve. Why 381? because 48 bytes per field element and remaining 3 bytes for flags or arithmetic optimisations.

Equation:

Key parameters of the curve are derived from a single parameter = -0xd201000000010000

  • Field modulus,
  • Subgroup size or the number of points on the curve,

Reason for such x:

  • low hamming weight, allows for efficient pairing operation
  • field modulus in 381 bits, efficient curve operation in 64 bit machines
  • subgroup size of 256 bits
  • curve security of 128 bits
  • nth root of unity for FFT

Field Extensions

The two curves used in BLS12-381 are defined on and . This power raised is known as an extension field of field .

Let’s construct , quadratic extension of . element representation also written as .

  • addition:
  • multiplication:

Understanding multiplication is a tricky thing and it takes time to get accustomed to field arithmetic. Basically, the original multiplication has a term which doesn’t make any sense in the field, so we need a mechanism to remove this term. This is where reduction of polynomial terms is used. Certain rules are used to reduce the polynomials having degree greater than 2. Rule in this case is

There are only 2 rules about this rule:

  1. the polynomial we’re reducing must be a degree polynomial, where is the extension degree.
  2. It must be irreducible in the field it is getting extended.

BLS12-381 consists of two curves: and . is a fairly simple curve defined over finite field . We can call this curve . Curve equation for is .

The other curve is defined over an extension of to . Since arithmetic on is fairly complex, it is reduced to . So, we’ll call this curve . Curve equation is slightly modified to be .

Subgroups

BLS12-381 is popular because it’s a pairing friendly curve. For pairings, we need two points from distinct groups, each of order . The first curve only has one subgroup of order , and thus we can’t just use that one curve. That’s why we require a second different curve which has a distinct subgroup of same order. Fortunately, this is exhibited by the curve defined over the extension field and one of these groups only contains points having a trace of zero. This is where , embedding degree comes in. Thus, we have group of order in , and a distinct group of same order in . This enables pairings.

Note: Trace of Zero

Twists

As explained earlier, that arithmetic on field is fairly complex and inefficient. And all the curve operations like add, sub, mul, etc. requires a lot of arithmetic. Thus, we need to transform the curve into a curve defined over a lower degree field that still has an order subgroup. Why we didn’t take this lower order field in the first place? Because we require subgroup having trace of zero points.

Quoting section 3 of this:

The basic idea for point compression is not only to restrict the first pairing argument to , but also to take the second argument as the image of a point on a sextic twist , where is an injective group homomorphism. This way one would work only with and for non-pairing operations like key generation, and map from to only when actually computing pairing values.

BLS12-381 uses a sextic twist. This means reducing the extension field degree by a factor of 6. We find a such that , then we define a twisting transformation as . This transforms the original curve from to . and looks different but actually are same objected with coefficients in different base fields.

This twist gives curve that has a subgroup of order that maps to our group. So, we can work over more efficient and map back to , when required.

Now, we have two groups:

  • where
  • where

Since, point in are complex numbers, it takes twice the amount of storage and are more expensive to perform arithmetic operations.

Embedding Degree

Smallest with respect to , where is a factor of the order of the curve, such that . Embedding Degree, is the smallest positive integer required to extend the field to satisfy conditions required for pairings.

  1. contains more than one subgroup of order for constructing .
  2. contains all the roots of unity for constructing .

Embedding Degree should be chosen such that it doesn’t compromise security and efficiency. Basically, a higher embedding degree makes it harder to to solve DLP in . But a higher embedding degree also make it harder to operations in higher field like . Maximum available twist is degree six, so best we can do is reduce the field extension degree by six.

Full Torsion Groups

Torsion group is a group where each element has finite order. -torsion group of an Elliptic curve is defined as set:

Now, for an elliptic curve with defined on extension field , the full -torsion group is defined as:

An interesting observation is, r-torsion group of a curve extension is equal to if power is less than the embedding degree of .

Cofactor

It’s the ratio of order of the curve group and order of the subgroup . Usually, cofactor should be very small in order to avoid subgroup attacks on discrete logarithms. But in pairing-based cryptography, the cofactors of , and can be very large.

By multiplying by the cofactor, a point on the curve is mapped to the appropriate group known as cofactor clearing. Cofactors for and are as follows:

Roots Of Unity

Roots of Unity are complex solutions to the equation: . Every nonzero element of a finite field is a root of unity, as for every nonzero element of .[^3]

Primitive root of unity is when a number is solution to but not for for any positive integer . So, if is a th primitive root of unity in a field , then contains all the roots of unity, .

Effect of the pairing is to map a point from and onto an th root of unity in . These th roots of unity form a subgroup in of order , which is the group .

Extension Towers

For BLS12-381, is constructed as a 2-3-2 extension tower, i.e. quadratic extension cubic extension quadratic extension.

  1. where . Point in looks like where . Reduction rule is which is irreducible in .
  2. where . Point in looks like where . Reduction rule: which is irreducible in .
  3. where . Point in looks like where . Reduction rule: which is irreducible in .

BLS Signatures