Overview

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\)
figure
Subroutine to find the order of a point with known factors
figure

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.

FAQ

What is the Weil pairing and why is it important in this chapter?The Weil pairing is a way to combine two elliptic-curve points of the same prime order into a field element with special algebraic properties. In this chapter, it is important because those properties can be used in cryptographic protocols, and because it provides a useful comparison point with other pairings such as the Tate pairing.
When should I use the Weil pairing instead of the Tate pairing?Use the Weil pairing when the two input points are not derived from the same base point and the protocol fits the Weil pairing’s requirements. If both pairing inputs come from the same base point, the Weil pairing becomes useless and the Tate pairing should be used instead.
What is the role of the reference point S in the Weil pairing formula?The reference point S is a third point used in the definition of the Weil pairing. It must not be in the same subgroup as the two points being paired. It helps make the formula well-defined and allows the pairing to be computed through the Miller function.
What does it mean that the Weil pairing is alternating?Alternating means that if the same point is used twice, the result is 1: e_m(T, T) = 1. It also means that swapping the two arguments inverts the result: e_m(P, Q) = e_m(Q, P)^(-1).
Why is swapping the two input points important for the Weil pairing?Because the order of the inputs matters. Swapping P and Q does not give the same result; instead, it gives the inverse. This symmetry is one of the distinctive properties of the Weil pairing.
How is the Weil pairing written in a more computation-friendly form?The chapter rewrites the pairing as e_m(P, Q) = [f_Q(-S) / f_P(S)] [f_P(Q+S) / f_Q(P-S)]. This form is easier to implement because it separates the Miller function evaluations into a pattern that can be computed directly in code.
What Miller function evaluations are needed to compute the Weil pairing in code?The implementation uses four Miller evaluations: f_P(Q+S), f_P(S), f_Q(P-S), and f_Q(-S). These are then combined as two fractions and divided to produce the final Weil pairing value.
Why does the chapter say the Weil pairing is useful for debugging code?Because the pairing has identities that should always hold. For example, different rearrangements of the formulas should produce the same answer. If the computed values do not match, that is a strong sign that there is a bug in the implementation.
Why do two points of order 11 produce an 11th root of unity?For points of order 11, the Weil pairing result must itself satisfy the order property. Raising the result to the 11th power should give 1, which means the output is an 11th root of unity.
Why is the Weil pairing useless for Diffie-Hellman public keys made from the same base point?If the two public keys are aT and bT for the same base point T, then e_m(aT, bT) = e_m(T, T)^(ab) = 1. So the pairing reveals no useful information because directly related points always pair to 1.

pro $24.99 per month

  • access to all Manning books, MEAPs, liveVideos, liveProjects, and audiobooks!
  • choose one free eBook per month to keep
  • exclusive 50% discount on all purchases
  • renews monthly, pause or cancel renewal anytime

lite $19.99 per month

  • access to all Manning books, including MEAPs!

team

5, 10 or 20 seats+ for your team - learn more


Close
choose your plan

team

monthly
annual
$49.99
$499.99
only $41.67 per month
  • five seats for your team
  • access to all Manning books, MEAPs, liveVideos, liveProjects, and audiobooks!
  • choose another free product every time you renew
  • choose twelve free products per year
  • exclusive 50% discount on all purchases
  • renews monthly, pause or cancel renewal anytime
  • renews annually, pause or cancel renewal anytime
  • Elliptic Curve Cryptography for Developers Elliptic Curve Cryptography for Developers ebook for free
Close
choose your plan

team

monthly
annual
$49.99
$499.99
only $41.67 per month
  • five seats for your team
  • access to all Manning books, MEAPs, liveVideos, liveProjects, and audiobooks!
  • choose another free product every time you renew
  • choose twelve free products per year
  • exclusive 50% discount on all purchases
  • renews monthly, pause or cancel renewal anytime
  • renews annually, pause or cancel renewal anytime
  • Elliptic Curve Cryptography for Developers Elliptic Curve Cryptography for Developers ebook for free
Close
choose your plan

team

monthly
annual
$49.99
$499.99
only $41.67 per month
  • five seats for your team
  • access to all Manning books, MEAPs, liveVideos, liveProjects, and audiobooks!
  • choose another free product every time you renew
  • choose twelve free products per year
  • exclusive 50% discount on all purchases
  • renews monthly, pause or cancel renewal anytime
  • renews annually, pause or cancel renewal anytime
  • Elliptic Curve Cryptography for Developers Elliptic Curve Cryptography for Developers ebook for free