The Weil pairing combines two elliptic-curve points of the same prime order m into a field-extension value that is an mth root of unity. It takes a third, reference point S whose order differs from m. This reference point keeps the Miller-function evaluations away from the paired subgroup. section 16.1 section 16.5
Equation 16.1
\[e_m(P, Q)=\dfrac{\dfrac{f_p(Q+S)}{f_p(S)}}{\dfrac{f_Q(P-S)}{f_Q(-S)}} \label{wq1}\]The formula evaluates Miller functions at shifts involving P, Q, and S. Its symmetric arrangement is the basis for the alternating and inverse-under-swap checks. section 16.1
For points P and Q, compute e_m(P,Q) from four Miller evaluations: f_P(Q+S), f_P(S), f_Q(P-S), and f_Q(-S). Divide the first pair, divide the second pair, then divide those intermediate results. Operationally, construct Q+S, -S, and P-S before invoking the Miller routine. section 16.2 section 16.1
Listing 16.1 Weil pairing routine
void weil(POLY *w, POLY_POINT P, POLY_POINT Q, POLY_POINT S, mpz_t m,
POLY_CURVE E)
{
POLY_POINT QpS, mS, PmS;
POLY t1, t2, t3, t4, w1, w2;
poly_point_init(&QpS); #1
poly_elptic_sum(&QpS, Q, S, E); #1
poly_point_init(&mS);
poly_copy(&mS.x, S.x); #2
poly_point_init(&PmS); #2
poly_sub(&mS.y, PmS.y, S.y); #2
poly_elptic_sum(&PmS, P, mS, E); #3
poly_init(&t1);
miller(&t1, P, QpS, m, E); #4
poly_init(&t2);
miller(&t2, P, S, m, E); #5
poly_init(&t3);
miller(&t3, Q, PmS, m, E); #6
poly_init(&t4);
miller(&t4, Q, mS, m, E); #7
poly_init(&w1);
poly_div(&w1, t1, t2); #8
poly_init(&w2); #8
poly_div(&w2, t3, t4); #8
poly_div(w, w1, w2); #8
poly_clear(&w1);
poly_clear(&w2);
poly_clear(&t1); #9
poly_clear(&t2); #9
poly_clear(&t3); #9
poly_clear(&t4); #9
poly_point_clear(&QpS); #9
poly_point_clear(&PmS); #9
poly_point_clear(&mS); #9
}
The routine maps the formula directly into point preparation, four Miller calls, two intermediate divisions, a final division, and cleanup. section 16.2
Use its distinctive results as both selection rules and implementation checks:
- Pairing a point with itself returns 1: e_m(T,T)=1. section 16.1 section 16.5
- Swapping inputs produces the inverse value: e_m(P,Q)=e_m(Q,P)^-1. section 16.1 section 16.5
- Directly related public keys aT and bT pair to 1, since e_m(aT,bT)=e_m(T,T)^(ab). section 16.4
- Protocols using different base points can use the Weil pairing; inputs sharing one base point require the Tate pairing instead. section 16.0
Aggregated-signature verification
An aggregate signature σ on G1 can be checked against generator g2 and aggregated public key A on G2 by testing e(σ,g2) = e(H0(m),A). Expanding σ and A reduces both sides to the same pairing raised to the summed signing scalars. section 18.2.3
Extension-curve cardinality can be computed from the trace of Frobenius and embedding degree using a recurrence. Factoring that cardinality may remain difficult for large field primes, a property associated here with the security of pairing-friendly curves. section 16.2 section 16.5
