16 Weil pairing defined
Weil pairings are introduced as a special kind of elliptic-curve pairing with properties that make them useful in some protocols and unsuitable in others. The key requirement is that the two paired points must come from the right kind of groups, while a third reference point must lie outside that subgroup. The chapter connects this idea to the Miller function from the earlier pairing material and emphasizes that Weil pairings can be used to validate calculations and help debug implementations, since the algebraic identities they satisfy should always hold if the code is correct.
The core definition is presented in terms of a reference point and two input points of prime order, producing a symmetric-looking expression built from Miller evaluations. From that definition come the main rules of the Weil pairing: it is alternating, so pairing a point with itself gives 1, and swapping the inputs inverts the result. The text then rewrites the formula into a form that is more convenient for computation and uses several equivalent identities to show that different algebraic arrangements must lead to the same outcome, providing a strong consistency check for implementations.
The implementation section turns the formula into code by computing four Miller values, combining them through division, and then cleaning up temporary variables. Supporting routines are also given for computing curve cardinalities over extension fields and for finding the order of points on both base and extension curves. A tiny worked example demonstrates how to choose points from the base and extension groups, how the pairing behaves for different combinations, and why some pairings are useless: if two public keys are derived from the same base point, the result collapses to 1. By contrast, mixing points from the intended groups produces meaningful roots of unity and confirms the expected pairing laws.
Relations between points \(P\), \(Q\) being paired and reference point \(S\)
Subroutine to find the order of a point with known factors
Summary
- The Weil pairing is computed using four calls to Miller’s algorithm. Two points of the same order \(m\) are paired, and a third reference point of different order is an input to the operation. The input values are field extension points, and the output is a field extension value that is an \(m^{th}\) root of unity.
- A Weil pairing of a point with itself gives a result of 1. Most other pairings do not have this property. Algorithms with multiple base points work well with Weil pairing.
- A Weil pairing will compute an inverse result if the input points are exchanged. That is, \[e_m(P, Q)=e_m(Q, P)^{-1}\]This is a very useful way to test that the code is working correctly.
- The cardinality of an extension curve is easy to compute. It may be exceptionally difficult to factor. For very large field primes, this inability to completely factor the cardinality increases the security of pairing-friendly curves.
Elliptic Curve Cryptography for Developers ebook for free