Weil pairing and Miller's algorithm

Question

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.

Answer 1

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?

Answer 2

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.