BLS12 - 381¶

Reference: BLS12-381

Motivation¶

BLS12-381 is a pairing-friendly elliptic curve. Here are some recommended readings on pairing-based cryptography:

Our document: elliptic curve.

Curve BLS12-381¶

Naming¶

BLS12-381 is part of a family of curves described by Barreto, Lynn, and Scott.

The number 12 represents the embedding degree of the curve.

The 381-bit modulus \(q\) represents coordinates on the curve. These coordinates derive from a finite field with a prime order.

Why 381 bits?

381 is quite convenient as we can utilize 48 bytes per field element, leaving 3 bits for flags or optimization.

This number’s size is determined by both security needs and implementation efficiency.

Curve Equation and Parameters¶

The basic equation of the BLS12-381 curve is:

\[ \begin{aligned} y^2 = x^3 + 4 \end{aligned} \]

The key parameters for a BLS curve are determined by a single parameter \(\chi\) (distinct from the \(x\) in the curve equation), which can be chosen to endow the curve with favorable properties for implementation.

BLS12-381 is derived from the \(k \equiv 0\) (mod 6) case of Construction 6.6 in the taxonomy.

Specific design goals:

\({\chi}\) has a “low hamming weight”, meaning very few bits are set to 1. This is crucial for the efficiency of the pairing calculation algorithm (Miller algorithm).
The field modulus \(q\) is prime and has 383 bits or fewer, enabling more efficient 64-bit or 32-bit arithmetic.
The order \(r\) of the subgroups we use is prime and has 255 bits or fewer, providing efficiency benefits similar to \(q\).
The security target is 128 bits.
To support zkSNARK schemes, a large power-of-two root of unity is desired in the filed \(F_r\).

This implies that we seek \(2^n\) as a divisor of \(r\) - 1, for some biggish \(n\). (Making \(\chi\) a multiple of \(2^{\frac{n}{2}}\) will achieve this).

This property is key to being able to use Fast Fourier Transforms for polynomial multiplication.

The value \(\chi\) = -0xd201000000010000 (hexadecimal, noting it is negative) provides the largest \(q\) and the lowest Hamming weight meeting these criteria.

With this \(\chi\) value we have:

Parameter	Denote	Equation	Value	Comments
Field modulus	\(q\)	\(\frac{1}{3}(x-1)^2(x^4-x^2+1) + x\)	0x1a0…aaab	381 bits, prime
Subgroup size	\(r\)	\((x^4 - x^2 + 1)\)	0x73e…000001	255 bits, prime
	\(a\)		0x00
	\(b\)		0x04
	\(\chi\)		0xd201000000010000

Field Extensions¶

The “12” in BLS12-381 not only represents the embedding degree but also the degree of extension fields.

Let’s construct \(F_{q^2}\), the quadratic extension of \(F_q\). In \(F_{q^2}\), we will represent field elements as first- degree polynomials like \(a_0 + a_1x\), which we can write more concisely as (\(a_0, a_1\)).

Let’s attempt this multiplication:

\[ \begin{array}{rcl} (a, b) \times (c, d) & = & (a + bx)(c + dx)\\ & = & ac + (ad + bc)x + bdx^2\\ \end{array} \]

We need a rule for reducing polynomials to ensure that they have a degree less than two.

For the equation above, we’re going to take \(x^2 + 1 = 0\) as our rule. There are only two rules about our rule:

The polynomial must have a degree \(k\), where \(k\) is our extension degree, which is 2 in this case.
It must be irreducible in the field we are extending. This implies that means it must not be factored into two or more lower degree polynomials.

Applying our rule, by substituting \(x^2 = -1\), gives us:

\[ \begin{aligned} (ac - bd) + (ad + bc)x = (ac - bd, ad + bc) \end{aligned} \]

In finite field, if we can find an irreducible \(k\)-degree polynomial in our field \(F_q\), we can extend the field to \(\mathbb{F_{q^{k}}}\), and represent the elements of the extended field as degree \(k - 1\) polynomials:

\[ \begin{aligned} a_0 + a_1x + ... + a_{k-1}x^{k-1} \end{aligned} \]

We can represent this compactly as:

\[ \begin{aligned} (a_0, ..., a_{k-1}) \end{aligned} \]

We can use Twists or Extension Towers) to reduce modularity.

The Curves¶

Actually, the BLS12-381 has two curves:

The first one is \(E(F_q)\) over the finite field \(F_q\)
The other curve, \(E'(F_{q^2})\), is defined over an extension fields of \(F_q\) to \(F_{q^2}\).

The Subgroups¶

Please review pairings or bilinear map section before proceeding to this section.

As we continue extending the field over which \(E\) is defined, it can be demonstrated that we eventually encounter a curve with more than one subgroup of order \(r\) (in fact, \(r\) + 1 subgroups).

Specifically, for some \(k\), \(E'(F_{q^k})\) contains other subgroups of order \(r\) that we can utilize.

One of these subgroups exclusively comprises points having a trace of zero, and we choose that subgroups to be \(G_2\).

Since both \(G_1\) in \(E(F_q)\) and \(G_2\) in \(E(F_{q^{12}})\) have the same order \(r\), we can now use them to do pairing.

Twists¶

Twist can transform \(E(F_{q^{12}})\) curve into a curve defined over a lower-degree field while retaining an order \(r\) subgroup.

Furthermore, this subgroup has a straightforward mapping to and from our \(G_2\) group.

BLS12-381 eomploys a “sextic twist” to reduce the degree of the extension field by a factor of six. So \(G_2\) on the twisted curve can be defined over \(E(F_{q^{2}})\) instead of \(E(F_{q^{12}})\).

If we find a \(u^{6} = (1 + i)^{-1}\), then we can define our twisting transformation as \((x, y) \to (x/u^{2}, y/u^{3})\). This transforms our original curve:

\(E: y^{2} = x^{3} + 4\)

\(E': y^{2} = x^{3} + 4/u^{6} = x^{3} + 4(i + 1)\)

These are the two groups we will be using:

\(G_1 \subset E(F_q)\) where \(E: y^{2} = x^{3} + 4\)

\(G_2 \subset E'(F_{q^{2}})\) where \(E': y^{2} + 4(1 + i)\)

Note

The coordinates of points in the \(G_1\) group are pairs of integers, and for \(G_2\) group are pairs of complex integers, so \(G_2\) points take twice the amount of storage, and more expensive to work with. This leads to interesting implementation tradeoffs.

Pairings¶

Please review pairings or bilinear map section before proceeding to this section.

From the properties of pairings, we can deduce that:

\(e([a]P, [b]Q) = e(P, [b]Q)^{a}\) \(= e(P, Q)^{ab} = e(P, [a]Q)^{b}\) \(= e([b]P, [a]Q)\)

This is what we need when verifying BLS Digital Signatures.

Embedding Degree¶

Please review embedding degree section before proceeding to this section.

The embedding degree provides the smallest field extension \(F_{q^{k}}\) that satisfies the two equivalent conditions:

\(\mathbb{F_{q^{k}}}\) contains more than one subgroup of order \(r\) (used for constructing \(G_2\), see The Subgroups).
\(\mathbb{F_{q^{k}}}\) contains all the \(r\) - th roots of unity (used for constructing \(G_T\), see Roots of Unity).

Regarding security, the embedding degree is also known as the security multiplier: a higher embedding degree makes the discrete logarithm problem harder to solve in \(G_T\).

However, a high embedding degree means we have to perform field operations in high-degree extensions, such as \(F_{q^{12}}\).

Security Level¶

Cryptographic system security is quantified in bits.

In elliptic curve cryptography, security is about making the discrete logarithm problem hard.

This entails ensuring that deducing \(k\) from given point \(g\) and \(g^{k}\) is infeasible without prior knowledge, requiring at least \(2^{n}\) computations.

For pairing-friendly curves, achieving \(n\) - bit security necessitates making the discrete logarithm problem difficult across all three groups employed. To achieve this:

The prime group order \(r\) must span least \(2n\) bits.
Our extended field \(F_{q^{k}}\) must be sufficiently large to withstand attacks like the number field sieve.

BLS12-381 was intended to provide approximately a 128 bits security level.

Cofactor¶

A subgroup’s cofactor is the ratio of the whole group’s size to the subgroup’s size.

Multiplying by the cofactor provides a simple method to map any arbitrary point on the elliptic curve into the respective subgroup \(G_1\) or \(G_2\).

Let denote the subgroup \(G\) with order \(r\), and its cofactor as \(h\), such that \(hr = n\), the order of the elliptic curve. Consider an arbitrary element \(P\) of the elliptic curve group. We have:

\(O = [n]P = [r] ([h]P)\)

Thus \([h]P \in G\).

This is crucial for operations like “hash to curve”: initially, we create a point on the curve, and then map it into the appropriate group by multiplying by the cofactor, so-called Cofactor Clearing.

For reference, the cofactors of \(G_1\) and \(G_2\) are as follows:

Group	Cofactor	Equation	Value (hexadecimal)
\(G_1\)	\(h_1\)	\((x-1)^2/3\)	0x396c…aaab
\(G_2\)	\(h_2\)	\((x^8 - 4x^7 + 5x^5 - 4x^4 + 6x^3 - 4x^2 - 4x + 13) / 9\)	0x5d5…e8e5

Using Curve¶

Warning

The content below has not been verified yet.

BLS Digital Signatures¶

The “BLS” in this section is different from the BLS above. Here, the “BLS” stands for: Boneh, Lynn and Shacham.

You can read more about BLS Digital Signatures over here and there.

Private and Public Key¶

The private/secret key \(s_k\) (used for signing) is simply a randomly selected number between 1 and \(r\) - 1 inclusive.

The corresponding public key is \(pk = [sk]g_1\), where \(g_1\) is the chosen generator point of \(G_1\). This means, \(g_1\) multiplied by \(sk\), which is \(g_1\) equivalent to adding \(g_1\) to itself \(sk\) times.

The discrete logarithm problem makes it unfeasible to recover \(sk\) from the public key \(pk\).

Signing¶

To sign a message \(m\), we first need to map \(m\) onto a point in group \(G_2\).

Refer to Hashing to the Curve for method. Once mapped, denote the resulting point in \(G_2\) as \(H(m)\).

We then sign the message by computing the signature \(\sigma = [sk]H(m)\) which involves multiplying the hash point by our secret key.

Verification¶

For a given message \(m\), signature \(\sigma\), and public key \(pk\), we aim to verify if it was signed with the \(sk\) corresponding to \(pk\).

This is facilitated by Pairings. The signature is valid if, and only if \(e(g_1, \phi) = e(pk, H(m))\).

We can validate this using pairing properties:

\(e(pk, H(m)) = e([sk]g_1, H(m))\) \(=e(g_1, H(m))^{(sk)} = e(g_1, [sk]H(m)) = e(g_1, \sigma)\)

Aggregation¶

To aggregate signatures, add up the respective \(G_2\) points:

\(\phi_{agg} = \phi_1 + \phi_2 + ... + \phi_n\)

Likewise, aggregate the corresponding \(G_1\) public key points:

\(pk_{agg} = pk_1 + pk_2 + ... + pk_n\)

To verify all the signatures together, check that \(e(g_1, \phi_{agg}) = e(pk_{agg}, H(m))\) using only two pairings.

Rogue Key Attacks¶

We must address the potential “rogue public key attack” when aggregating signatures for the same message.

Swapping \(G1\) and \(G2\)¶

For digital signatures, the \(G_1\) and \(G_2\) groups are interchangeable.

For ZCash, they use \(G_1\) for signatures and \(G_2\) for public keys.

In other implementations, the usage of \(G_1\) and \(G_2\) may be “reversed”.

Point Compression¶

Subgroup Membership Checks¶

It’s important to verify that point lies in the correct subgroup.

Subgroup checks are simple: simply multiply our point by \(r\).

For points in \(G_1\) or \(G_2\), this will result in the respective points at infinity. For points outside the groups, it won’t.

You can read new techniques for faster subgroup checks.

Generator Point¶

Read Generator Point.

Final Exponentiation¶

Read the Tate pairing to understand the Miller and final exponentiation processes.

To verify a signature, conduct two Miller loops - one with a negated input value - multiply the results and then perform a single final exponentiation.

If the result is unity in \(G_T\), our pairings match.

Hashing to the Curve¶

To generate a digital signature for a message, we initially transform the message into a point on the \(G_2\) curve (if \(G_2\) is used for signatures).

Hash and Check¶

Steps:

Hash your message to an integer modulo \(q\)
Verify if there exist a point on the curve with this \(x\)-coordinate. If not, add one and repeat
We obtain a point on the curve. Multiply it by the \(G_2\) cofactor to convert it into a point in \(G_2\).

Simplified SWU Map¶

Read here.

Extension Towers¶

Specifically:

\(F_{q^2}\) is constructed as \(F_q(u)/(u^2 - \beta)\) where \(\beta = -1\).
\(F_{q^6}\) is constructed as \(F_{q^2}(v)/(v^2 - \xi)\) where \(\xi = u + 1\).
\(F_{q^{12}}\) is constructed as \(F_{q^6}(w)/(w^2 - \gamma)\) where \(\gamma = v\).

This towered extension can replace the direct extension as a basis for pairings.

When implemented effectively, it can significantly reduce arithmetic operations when multiplying point in \(F_{q^{12}}\).