3
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$ Jun 27, 2011 at 18:30
  • $\begingroup$ Argh. Of course it's Joe Silverman. I'm an idiot. $\endgroup$ Jun 27, 2011 at 19:31
  • $\begingroup$ 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. $\endgroup$
    – Aeryk
    Jun 27, 2011 at 19:40

2 Answers 2

5
$\begingroup$

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?

$\endgroup$
4
  • $\begingroup$ @Joe... Argh... Sorry! In fact, there really was Ed Silverman, a professor at Purdue. $\endgroup$ Jun 27, 2011 at 19:29
  • $\begingroup$ (Actually, Ed Silverman was a math prof at Purdue some decades ago, is how the name got into my head... But, still, sorry!) $\endgroup$ Jun 27, 2011 at 19:32
  • $\begingroup$ Thank's, I'll definitely look into that. Meanwhile, I think I found a simple argument, see my answer below. $\endgroup$
    – Jasiu
    Jun 27, 2011 at 20:20
  • 1
    $\begingroup$ @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!) $\endgroup$ Jun 27, 2011 at 21:04
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.