Make Weil pairing polynomial time

[davidjao]

The Weil pairing implementation in Sage is horribly inefficient when the group order n is a cryptographically large composite integer.

The implementation is based on Miller's algorithm, which in its original version is a polynomial time algorithm, capable of handling large composite values of n. However, the Sage implementation attempts to determine the order of the input points P and Q. The problem of determining the order of a point on an elliptic curve of large composite order is conjectured to be computationally infeasible (Boneh-Goh-Nissim TCC'05), and all known methods for solving this problem require factoring n.

Therefore, by adding the order computation, the Weil pairing calculation is transformed from a polynomial time algorithm to a superpolynomial time algorithm requiring the factorization of n.

I propose to delete the code block that contains the order computation, since the order computation is not useful when n is prime, and is inefficient when n is composite. Note that we still check to ensure P and Q are n-torsion -- this patch simply deletes the code to compute their exact order. The attached file implements this change.

CC: @JohnCremona

Component: elliptic curves

Keywords: Weil pairing

Author: David Jao

Reviewer: Aly Deines

Merged: sage-4.6.2.alpha1

Issue created by migration from https://trac.sagemath.org/ticket/10523

[kini]

comment:2

Mightn't it be wise to leave a comment in place of the deleted code block to warn people not to add similar code again (maybe a citation of Boneh-Goh-Nissim TCC'05, which you referenced in your sage-devel post)?

[7c09a680-e216-4024-bb8e-9bfd4aa7f313]

comment:3

Replying to @kini:

Mightn't it be wise to leave a comment in place of the deleted code block to warn people not to add similar code again (maybe a citation of Boneh-Goh-Nissim TCC'05, which you referenced in your sage-devel post)?

That's a very sensible thing to do. That is, don't just delete bad code, but comment it out and provide an explanation why it shouldn't be used.

[davidjao]

Attachment: trac_10523_weil_pairing_performance_fix.patch.gz

[davidjao]

comment:5

Replying to @sagetrac-mvngu:

Replying to @kini:

Mightn't it be wise to leave a comment in place of the deleted code block to warn people not to add similar code again (maybe a citation of Boneh-Goh-Nissim TCC'05, which you referenced in your sage-devel post)?

That's a very sensible thing to do. That is, don't just delete bad code, but comment it out and provide an explanation why it shouldn't be used.

I updated the patch to comment out the code, and added the explanation as well.

[kini]

comment:6

Great!

By the way, I noticed in your sage-devel thread you mentioned you are learning how to use Mercurial - so am I, and here's something I've learned. Rather than committing your changes, exporting the changeset as a diff, naming it foobar.patch, and uploading it to trac, you can use the mq extension. (Your patch has a Node ID in it, which leads me to believe you are not using mq -- if you are, just ignore the rest of this comment...)

First enable it by adding "[extensions]\nmq = " to a relevant hgrc file, such as ~/.hgrc . Then simply start with the Mercurial repository you want to patch updated to the latest dev release of sage (4.6.1.rc0 right now, I think), then make whatever changes, and then run in this case hg qnew -UDm "#10523: Remove superpolynomial-time order computation from Weil pairing" trac_10523_weil_pairing_performance_fix.patch. This will create a patch in $(hg root)/.hg/patches with the appropriate filename which you can just upload directly, as well as committing to the local hg repository. However, unlike in normal Mercurial, you can then use hg qpop to undo your patch on the actual files in the directory and undo the commit, and hg qpush to redo them. If you want to update your patch, hg qpush it first, then make some changes, and then use hg qrefresh. This will automatically update your patch file (and the commit mq had made to the repository), which is easier than having to undo and redo normal Mercurial commits. You can actually create more patches with hg qnew after pushing your first one, which will then be calculated with the first patch as a base, etc. etc. - run hg help mq for more info.

Hope that helps you as much as it helped me.

[4dfe6752-6233-4f7f-8e0e-e1363b12c1b7]

Reviewer: Aly Deines

[jdemeyer]

Merged: sage-4.6.2.alpha1