# Weil pairing and Miller's algorithm

I'm studying Weil pairing and its applications in cryptography. I already know that it can be defined like this:

$$w(P, Q) = (-1)^n\frac{f_P(Q)}{f_Q(P)}\frac{f_Q}{f_P}(\mathcal{O})$$

where

$\textrm{div}(f_P) = n(P) - n(\mathcal{O})$ and $\textrm{div}(f_Q) = n(Q) - n(\mathcal{O})$.

This is not suitable for computation, so we shift the numerator by $R$ and the denominator by $S$ and we obtain:

$$w(P, Q) = (-1)^n\frac{g_P(Q+S)}{g_Q(P+R)}\frac{g_Q(R)}{g_P(S)}$$

where

$\textrm{div}(g_P) = n(P+R) - n(\mathcal{R})$ and $\textrm{div}(g_Q) = n(Q+S) - n(\mathcal{S})$.

Enter Miller's algorithm. In order to calculate $g_P(A)$ we define $h_k$ for $k = 0,\ldots,n$ as:

$$\textrm{div}(h_k) = k(P+R) - k(R) - (kP) + \mathcal{O}$$

Now, $h_n = g_P$ and we can calculate $h_{k+l}(A)$ from $h_k(A)$ and $h_l(A)$. So we construct a "double-and-add" algorithm similar to fast exponentiation.

Although $g_P(A)$ is never zero or infinity (for $A = Q+S$ or $A = S$), it can happen that during the execution of "double-and-add" algorithm we can encounter some $h_k(A)$ equal to zero or infinity. The solution is to randomly select new $Q$ and $S$ and start over.

How do I prove that there exist such $Q$ and $S$ that I will be able to calculate the Weil pairing of $P$ and $Q$?

If possible, I'd like to see some simple argument that does not refer to algebraic geometry, as I don't know anything about it - I come from cryptography.

-
I fear that any legitimate proof that the algorithm succeeds after relatively few re-starts, or even that there exists a choice that would succeed, will require a little serious consideration of how elliptic curves work. Not "algebraic geometry", really. Ed Silverman has several books about elliptic curves addressing a range of audiences, starting with one with minimal prerequisites. –  paul garrett Jun 27 '11 at 18:30
Argh. Of course it's Joe Silverman. I'm an idiot. –  paul garrett Jun 27 '11 at 19:31
I think I recall that the additive group is the direct product of two cyclic groups or something similar. So you choose points in the "other half" (for the algorithm probabilistically they have high enough order, for the proof one exists with high enough order) so that no collisions/interactions happen. –  Aeryk Jun 27 '11 at 19:40

I had thought that if suitably formulated, Miller's algorithm works without having to go back and recompute if some intermediate point turns out to be the point at infinity. Miller's algorithm is described in many books, but I'll point for example to the 2nd edition of my Arithmetic of Elliptic Curves (Springer GTM 106, 2009). The algorithm is described in Figure 11.6 on page 394, where note that the formula for $h_{P,Q}$ on that page depends on whether the relevant slope is finite or infinite. I'm not really an algorithms person, so there are likely to be ways to make the computation more efficient than what I described. And as a final note, there's an alternative way to compute the Weil and Tate pairings using elliptic divisibility sequences (nets) due to Kate Stange, The Tate pairing via elliptic nets, Pairing-Based Cryptography -- PAIRING 2007, Springer LNCS 4575 (2007), 329-348 [http://eprint.iacr.org/2006/392].

@Paul Garrett: Who is "Ed" Silverman?

-
@Joe... Argh... Sorry! In fact, there really was Ed Silverman, a professor at Purdue. –  paul garrett Jun 27 '11 at 19:29
(Actually, Ed Silverman was a math prof at Purdue some decades ago, is how the name got into my head... But, still, sorry!) –  paul garrett Jun 27 '11 at 19:32
Thank's, I'll definitely look into that. Meanwhile, I think I found a simple argument, see my answer below. –  Jasiu Jun 27 '11 at 20:20
@Paul: Not a problem, I figured it was a slip of the keyboard. So Edward Silverman (Ph.D. University of California, Berkeley 1948) had two PhD students at Purdue in the 1970s. (The math genealogy project is such fun!) –  Joe Silverman Jun 27 '11 at 21:04

In order to calculate $h_{k+l}(A)$ from $h_k(A)$ and $h_l(B)$ you have to evaluate lines $l_1$ and $l_2$ at point $A$, where $l_1$ passes through $kP$ and $lP$ and $l_2$ is a vertical line through $(k+l)P$. The "double-and-add" algorithm takes $log_2(n)$ steps to compute $h_n(A)$, so only $O(log_2(n))$ points of form $mP$ are involved when determining lines $l_1$ and $l_2$ at various steps of the algorithm. There are certainly more points on an elliptic curve than that.

-