RSS preview of John D. Cook

Rss preview of Blog of John D. Cook

Elliptic curve pairings in cryptography

2025-11-17 04:27:09

Pairings can mean a variety of related things in group theory, but for our purposes a pairing is a bilinear mapping from two groups to a third group.

e: G₁ × G₂ → G_T

Typically the group operation on G₁ and G₂ is written addititvely and the group operation on G_T is written multiplicatively. In fact, G_T will always be the multiplicative group of a finite field, i.e. G_T consists of the non-zero elements of a finite field under multiplication. (The “T” stands for “target.”)

Here bilinear means that if x is an element of G₁ and y is an element of G₂ , and a and b are nonnegative integers,

e(ax, by) = e(x, y)^ab.

There are a few provisos …

First, the pairing must be non-trivial, i.e. e(p, q) ≠ 1 for some p and q.

Second, the pairing must be efficiently computable.

Third, the embedding degree must not be “too high.” This means that if G_T is the multiplicative group of a field with p^k elements, k is not too big. We will look at two examples in which k = 12.

The second and third provisos are important even though they’re not stated rigorously.

Cryptography often speaks of pairing elliptic curves, but in fact it uses pairings of prime-order subgroups of the additive groups of elliptic curves. Because the subgroups have prime order, they are cyclic, and so the pairing is determined by its value on a generator from each subgroup.

Example: BN254

The previous post briefly mentioned a pairing between two elliptic curves, BN254 and alt_bn128, that is used in Ethereum and was used in Zcash in the original Sprout shielded protocol.

The elliptic curve BN254 is defined over the field F_p, the integers mod p, where

p = 21888242871839275222246405745257275088696311157297823662689037894645226208583.

and the elliptic curve alt_bn128 is defined over the field F_p[i], i.e. the field F_p, with an imaginary element i adjoined.

Both elliptic curves have a subgroup of order

r = 21888242871839275222246405745257275088548364400416034343698204186575808495617,

which is prime. So in the pairing the groups G₁ and G₂ are isomorphic to the integers mod r. The target group G_T has order p12 − 1 and so the embedding degree k equals 12, and so the embedding degree is “not too high.”

Example: BLS12-381

Another example also comes from Ethereum and Zcash. Ethereum uses BN254 in smart contracts, but it uses BLS12-381 in its consensus layer. Zcash switched from BN254 to BLS12-381 in the Sapling release.

BLS12-381 is defined over a prime order field with on the order of 2³⁸¹ elements and has embedding order 12, hence 12-381. The BLS stands for Paulo Barreto, Ben Lynn, and Michael Scott. Elliptic curve names often look mysterious, but they’re actually pretty descriptive. I discuss BLS12-381 in more detail here. As in the example above, BLS12-381 is defined over a field F_p and is paired with a curve over F_p[i], i.e. the same field with an imaginary element adjoined. The equation for BLS12-381 is

y² = x³ + 4

and the equation for the curve it is paired with is

y² = x³ + 4(1 + i)

As before the target group is the multiplicative group of a finite field of order p¹².

The post Elliptic curve pairings in cryptography first appeared on John D. Cook.

Adding an imaginary unit to a finite field

2025-11-17 03:13:04

Let p be a prime number. Then the integers mod p form a finite field.

The number of elements in a finite field must be a power of a prime, i.e. the order q = pⁿ for some n. When n > 1, we can take the elements of our field to be polynomials of degree n − 1 with coefficients in the integers mod p.

Addition works just as you’d expect addition to work, adding coefficients mod p, but multiplication is a little more complicated. You multiply field elements by multiplying their polynomial representatives, but then you divide by an irreducible polynomial and take the remainder.

When n = 2, for some p you can define the field by adding an imaginary unit.

When you can and cannot adjoin an i

For some finite fields of order p, you can construct a field of order p² by joining an element i to the field, very much the way you form the complex numbers from the real numbers. For example, you can create a field with 49 elements by taking pairs of (a, b) of integers mod 7 and multiplying them as if they were a + bi. So

(a, b) * (c, d) = (ac − bd, ad + bc).

This is equivalent to choosing the polynomial x² + 1 as your irreducible polynomial and following every polynomial multiplication by taking the remainder modulo x² + 1.

This works for a field with 49 elements, but not for a field of 25 elements. That’s because over the integers mod 5 the polynomial x² + 1 already has a root. Two of them in fact: x = 2 or x = 3. So you could say that mod 5, i = 2. Or i = 3 if you prefer. You can still form a field of 25 elements by taking pairs of elements from a field of 5 elements, but you have to choose a different polynomial as your irreducible polynomial because x² + 1 is not irreducible because

x² + 1 = (x − 2)(x + 2)

when working over the integers mod 5. You could use

x² + x + 1

as your irreducible polynomial. To prove that this polynomial is irreducible mod 5, plug in the numbers 0, 1, 2, 3, and 4 and confirm that none of them make the polynomial equal 0.

In general, you can create a field of order p² by adjoining an element i if and only if p = 3 mod 4.

Next we’ll look at an example of making a very large finite field even larger by adding an imaginary element.

Example from Ethereum

The Ethereum virtual machine has support for a pairing—more on that in a future post—of two elliptic curves, BN254 and alt_bn128. The BN254 curve is defined by

y² = x³ + 3

over the field F_p, the integers mod p, where

p = 21888242871839275222246405745257275088696311157297823662689037894645226208583.

The curve alt_bn128 is defined by

y² = x³ + 3/(9 + i)

over the field F_p[i], i.e. the field F_p, with an element i adjoined. Note the that last two digits of p are 83, and so p is congruent to 3 mod 4.

Special point on curve

The Ethereum documentation (EIP-197) singles out a particular point (x, y) on alt_bn128:

x = a + bi
y = c + di

where

a = 10857046999023057135944570762232829481370756359578518086990519993285655852781
b = 11559732032986387107991004021392285783925812861821192530917403151452391805634
c = 8495653923123431417604973247489272438418190587263600148770280649306958101930
d = 4082367875863433681332203403145435568316851327593401208105741076214120093531.

We will show that this point is on the curve as an exercise in working in the field F_p[i]. We’ll write Python code from scratch, not using any libraries, so all the details will be explicit.

def add(pair0, pair1, p):
    a, b = pair0
    c, d = pair1
    return ((a + c) % p, (b + d) % p)

def mult(pair0, pair1, p):
    a, b = pair0
    c, d = pair1
    return ((a*c - b*d) % p, (b*c + a*d) % p)

p = 21888242871839275222246405745257275088696311157297823662689037894645226208583
a = 10857046999023057135944570762232829481370756359578518086990519993285655852781
b = 11559732032986387107991004021392285783925812861821192530917403151452391805634
c = 8495653923123431417604973247489272438418190587263600148770280649306958101930
d = 4082367875863433681332203403145435568316851327593401208105741076214120093531

# Find (e, f) such that (e, f)*(9, 1) = (1, 0).
# 9e - f = 1
# e + 9f = 0
# Multiply first equation by 9 and add.
e = (9*pow(82, -1, p)) % p
f = (-e*pow(9, -1, p)) % p
prod = mult((e, f), (9, 1), p)
assert(prod[0] == 1 and prod[1] == 0)

y2 = mult((c, d), (c, d), p)
x3 = mult((a, b), mult((a, b), (a, b), p), p)
rhs = add(x3, mult((3, 0), (e, f), p), p)

assert(y2[0] == rhs[0])
assert(y2[1] == rhs[1])

The post Adding an imaginary unit to a finite field first appeared on John D. Cook.

Four generalizations of the Pythagorean theorem

2025-11-13 23:25:33

Here are four theorems that generalize the Pythagorean theorem. Follow the links for more details regarding each equation.

1. Theorem by Apollonius for general triangles.

2. Edsgar Dijkstra’s extension of the Pythagorean theorem for general triangles.

$\text{sgn}(\alpha + \beta - \gamma) = \text{sgn}(a^2 + b^2 - c^2)$

3. A generalization of the Pythagorean theorem to tetrahedra.

$V_0^2 = \sum_{i=1}^n V_i^2$

4. A unified Pythagorean theorem that covers spherical, plane, and hyperbolic geometry.

$A(c) = A(a) + A(b) - \kappa \frac{A(a) \, A(b)}{2\pi}$

The post Four generalizations of the Pythagorean theorem first appeared on John D. Cook.

Elementary symmetric polynomials and optimization

2025-11-12 22:55:40

The mth elementary symmetric polynomial of degree n

$e_m(x_1, x_2, \ldots, x_n)$

is the sum of all terms containing a product of m variables. So, for example,

$\begin{align*} e_1(w, x, y, z) &= w + x + y + z \\ e_2(w, x, y, z) &= wx + wy + wz + xy + xz + yz \\ e_3(w, x, y, z) &= xyz + wyz + wxz + wxy \\ e_4(w, x, y, z) &= wxyz \end{align*}$
These polynomials came up in the previous post. The problem was choosing weights to minimize the variance of a weighted sum of random variables can be solved using elementary symmetric polynomials.

To state the optimization problem more generally, suppose you want to minimize

$t_1^2 x_1 + t_2^2x_2 + \cdots + t_n^2 x_n$

where the t_i and x_i are positive and the t_i sum to 1. You can use Lagrange multipliers to show that the solution is

$t_i = \frac{e_n(x_1, x_2, \cdots, x_n)}{x_i \,e_{n-1}(x_1, x_2, \cdots, x_n)}$

The post Elementary symmetric polynomials and optimization first appeared on John D. Cook.

Weighting an average to minimize variance

2025-11-12 21:02:54

Suppose you have $100 to invest in two independent assets, A and B, and you want to minimize volatility. Suppose A is more volatile than B. Then putting all your money on A would be the worst thing to do, but putting all your money on B would not be the best thing to do.

The optimal allocation would be some mix of A and B, with more (but not all) going to B. We will formalize this problem and determine the optimal allocation, then generalize the problem to more assets.

Two variables

Let X and Y be two independent random variables with finite variance and assume at least one of X and Y is not constant. We want to find t that minimizes

$\text{Var}[tX + (1-t)Y]$

subject to the constraint 0 ≤ t ≤ 1. Because X and Y are independent,

$\text{Var}[tX + (1-t)Y] = t^2 \text{Var}[X] + (1-t)^2 \text{Var}[Y]$

Taking the derivative with respect to t and setting it to zero shows that

$t = \frac{\text{Var}[Y]}{\text{Var}[X] + \text{Var}[Y]}$

So the smaller the variance on Y, the less we allocate to X. If Y is constant, we allocate nothing to X and go all in on Y. If X and Y have equal variance, we allocate an equal amount to each. If X has twice the variance of Y, we allocate 1/3 to X and 2/3 to Y.

Multiple variables

Now suppose we have n independent random variables X_i for i running from 1 to n, and at least one of the variables is not constant. Then we want to minimize

$\text{Var}\left[ \sum_{i=1}^n t_i X_i \right] = \sum_{i=1}^n t_i^2 \text{Var}[X_i]$

subject to the constraint

$\sum_{i=1}^n t_i = 1$

and all t_i non-negative. We can solve this optimization problem with Lagrange multipliers and find that

$t_i \text{Var}[X_i] = t_j \text{Var}[X_j]$

for all 1 ≤ i, j ≤ n. These (n − 1) equations along with the constraint that all the t_i sum to 1 give us a system of equations whose solution is

$t_i = \frac{\prod_{j \ne i} \text{Var}[X_j]}{\sum_{i = 1}^n \prod_{j \ne i} \text{Var}[X_j]}$

Incidentally, the denominator has a name: the (n − 1)st elementary symmetric polynomial in n variables. More on this in the next post.

The post Weighting an average to minimize variance first appeared on John D. Cook.

Brownian motion and Riemann zeta

2025-11-11 03:14:08

Excellent video by Almost Sure: What does Riemann Zeta have to do with Brownian Motion?

Connects several things that I’ve written about here including Brownian motion, the Riemann zeta function, and the Kolmogorov-Smirnov test.

The post Brownian motion and Riemann zeta first appeared on John D. Cook.

John D. Cook Modify

Rss preview of Blog of John D. Cook

Example: BN254

Example: BLS12-381

Related posts

When you can and cannot adjoin an i

Example from Ethereum

Special point on curve

Related posts

Related posts

Two variables

Multiple variables

Related posts

John D. CookModify

Rss preview of Blog of John D. Cook

Example: BN254

Example: BLS12-381

Related posts

When you can and cannot adjoin an i

Example from Ethereum

Special point on curve

Related posts

Related posts

Two variables

Multiple variables

Related posts

The author's social media

John D. Cook Modify