Re: [sage-devel] EC pairing framework

[John Cremona]

I am interested in this. Might I suggest that sage-nt would be a better forum?

Apart from the things you picked up on, there was also some code
written by Nadia who spoke at the Sage Days in Nancy. I'm not sure if
she posted that on sage-* but I think it is on trac. Must run,

John Cremona

2009/1/11 David Møller Hansen <da...@mollerhansen.com>:
>
> This is a call out to the people who is interested in getting pairings
> on elliptic curves into Sage.
>
> I have started a Ticket #4964 on getting a pairing framework into
> Sage.
>
> Currently I am trying to get an overview of what activity there is on
> this in Sage.
>
> I've browsed the TRAC server and this forum I found the following
>
> * Ticket #1236: add Tate pairing to Sage.
>
> * Discussion on getting Ben Lynn's pbc library licensed s.t. it can be
> wrapped into Sage.
>
> * Discussion on writing a wrapper for John Cremona's mwrank and gp
> scripts implementation of the Weil and Tate pairing.
>
> * Self started discussion on where pairings should be placed in Sage,
> resulting in WWMD (What Would Magma Do).
> >
>

[David Møller Hansen]

From the discussion in thread
http://groups.google.com/group/sage-devel/browse_thread/thread/b14982...
Pairing function should be placed on a point as in Magma.
I will use the Miller algorithm to compute the functions needed to
compute the Weil pairing.
I will place Millers algorithm in seperate Miller.py file but I want
to call it from a function in ell_point.py.
I have a question regarding the code in ell_point.py:
I guess the pairing should work on points over a general field, but
in
ell_point.py the implementation of points is divided into field,
number field and finite field class instances.
If you place it on the class field, will it then be inherited by the
number field and finite field classes? Or would you place it in each
class?
Thanks.

[David Møller Hansen]

I will just repost my latest post in the former thread.

From the discussion in thread
http://groups.google.com/group/sage-devel/browse_thread/thread/b14982...
Pairing function should be placed on a point as in Magma.
I will use the Miller algorithm to compute the functions needed to
compute the Weil pairing.
I will place Millers algorithm in seperate Miller.py file but I want
to call it from a function in ell_point.py.
I have a question regarding the code in ell_point.py:
I guess the pairing should work on points over a general field, but
in
ell_point.py the implementation of points is divided into field,
number field and finite field class instances.
If you place it on the class field, will it then be inherited by the
number field and finite field classes? Or would you place it in each
class?
Thanks.

On Jan 11, 7:13 pm, "John Cremona" <john.crem...@gmail.com> wrote:

[David Møller Hansen]

Thanks

Found the Nadia talk - but how can I find on trac?

/David

On Jan 11, 7:13 pm, "John Cremona" <john.crem...@gmail.com> wrote:

[John Cremona]

On 11 Jan, 18:28, David Møller Hansen <da...@mollerhansen.com> wrote:
> I will just repost my latest post in the former thread.
>

> From the discussion in threadhttp://groups.google.com/group/sage-devel/browse_thread/thread/b14982...

> Pairing function should be placed on a point as in Magma.
> I will use the Miller algorithm to compute the functions needed to
> compute the Weil pairing.
> I will place Millers algorithm in seperate Miller.py file but I want
> to call it from a function in ell_point.py.
> I have a question regarding the code in ell_point.py:
> I guess the pairing should work on points over a general field, but
> in
> ell_point.py the implementation of points is divided into field,
> number field and finite field class instances.
> If you place it on the class field, will it then be inherited by the
> number field and finite field classes? Or would you place it in each

It's enough to put the function into the top-most relevant class, in
this case the class EllipticCurvePoint_field. Then the function is
automatically inherited by the subsidiary classes. At the same time,
if there was a special algorithm which only applied over finite fields
(say), you could also put in a function to the class
EllipticCurvePoint_finite_field and that would be used for points over
finite fields. That is the way python works: it goes up the tree and
uses the first match it finds, so special methods can (in effect)
overwrite general methods.

How general do you intend to make this? We could have P.weil_pairing
(Q) defined whenever P and Q both had finite order, the result being a
d'th root of unity where d = gcd(P.order(), Q.order()), with an
exception being raised if either point has infinite order. The result
should be in the common field of definiton of the curve on which both
P and Q lie (they must lie on the same curve).

Or, as a special case, we could have P.m_weil_pairing(Q) where P and Q
are on the same curve and m*P==m*Q==0 would be a requirement.

Or we could also have a version for the phi-Weil pairing where phi is
an isogeny, and P and Q are on different though phi-isogenous curves.
I suspect that this case should wait, given that isogenies are not at
all implemented in Sage yet.

My gp script uses the Miller functions, as does my C++ code (which is
in eclib). It makes no claims to be efficient for anything of
cryptographic size; but on the other hand of you ever ask for the
generators of a curve over QQ, then in the background mwrank runs and
uses this code (applied to various reductions of the curve modulo
primes) when saturating the basis. Both those implementations are
only over prime fields, but for trivial reasons; the code is
essentially generic.

I will look for the code which Nadia sent me and post it here.

John

[David Møller Hansen]

> How general do you intend to make this?

I have some Sage code that handles the special case where P,Q is both
of order m. Though I actually haven't tried it, since I originally
implemented the code to work in a crypto scheme, I believe that the
Miller algorithm works fine for P,Q just having finite order.

> We could have P.weil_pairing
> (Q) defined whenever P and Q both had finite order, the result being a
> d'th root of unity where d = gcd(P.order(), Q.order()), with an
> exception being raised if either point has infinite order.

Yes, I agree. I will do it i this way.

> I will look for the code which Nadia sent me and post it here.

Thanks.

David

[John Cremona]

2009/1/11 David Møller Hansen <da...@mollerhansen.com>:
>

>> How general do you intend to make this?
>
> I have some Sage code that handles the special case where P,Q is both
> of order m. Though I actually haven't tried it, since I originally
> implemented the code to work in a crypto scheme, I believe that the
> Miller algorithm works fine for P,Q just having finite order.

OK. I think it is true that if P and Q have orders m,n and d=gcd(m,n)
then it's certainly clear that <P,Q> is a d'th root of unity, and
moreover <P,Q>=<(m/d)*P,(n/d)*Q>, so my slightly more general case
reduces to the one you have implemented easily. [This fact is not too
hard to prove; Silverman has a special case only, when m|n. I have
not looked elsehere.]

It is probably worth implementing very small cases (including 2,3,4) separately.

I just remembered that my code did use random point creation: does yours?

>
>> We could have P.weil_pairing
>> (Q) defined whenever P and Q both had finite order, the result being a
>> d'th root of unity where d = gcd(P.order(), Q.order()), with an
>> exception being raised if either point has infinite order.
>
> Yes, I agree. I will do it i this way.

Excellent: will you submit a patch to ell_point.py?

>
>> I will look for the code which Nadia sent me and post it here.
>

I found that she had emailed the code to me directly after the Sage
meeting. So I have asked her if I can post it.

John

[David Møller Hansen]

> It is probably worth implementing very small cases (including 2,3,4) separately.

Yes, I have not thought about these cases that much, since I've been
doing it with crypto in mind, but the cases should definitely be
handled.

> I just remembered that my code did use random point creation: does yours?

Yes and no, I have implemented two cases, the random case like you,
which is slow since I test for lin. independence of the random point P
by checking for division with zero by running through the algorithm.

And no, since I also implemented a version that, when you know you
have a linear independent points P,Q you do not need the random point
and you can just compute:

e_n = ((-1)^n)*(f_n(P,Q)/f_n(Q,P))

> Excellent: will you submit a patch to ell_point.py?

Yes I hope to do so late this month, I've been a bit tied up the last
couple of weeks and will also be so next week.

> I found that she had emailed the code to me directly after the Sage
> meeting. So I have asked her if I can post it.

Think I saw your post with the code, I'll have a look at it. Thanks!

David

[David Møller Hansen]

> I found that she had emailed the code to me directly after the Sage
> meeting. So I have asked her if I can post it.

I've read the code and I pretty much agree with her, I'm just
concerned about her line function, she returns the value 1 in the case
where P_1 or P_2 both equal O but I would think that the line would
have value x(P_1) - x(Q) when P_2 = O and P_1 \neq O.

But she do not divide into lin. dep. and lin. indep. cases when she
compute e_n = ((-1)^n)*(f_n(P,Q)/f_n(Q,P)).

I can't reallly wrap my head around why it could work now, but if it
does then it would be really nice!

David

[David Møller Hansen]

> where P_1 or P_2 both equal O but I would think that the line would

this line should have been without the "both":

where P_1 or P_2 equal O but I would think that the line would.

David

On Jan 17, 2:52 pm, David Møller Hansen <da...@mollerhansen.com>

[John Cremona]

I agree with your comments.

You can find the special code for n=2,3,4 in
sage-*/data/extcode/pari/cremona/ell_weil.gp (assuming the the gp
script is legible to you), And the functions for tangents, chords,
vertical lines etc are defined in ell_ff.gp in the same place: withe
prefix ellff (for "elliptic curve function field) they are
(ellff)vert, tang, chord, addpol, multpol, each one defined properly
in terms of the divisor of the function. Each one has a sort of
docstring like this:


\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\
\\ ellffaddpol(e,t,s) returns [s+t,h] where h's divisor is
\\ (t)+(s)-(s+t)-(0)
\\ i.e. the function "proving" s+t is correct
\\ if s=-t this degenerates to ellffvert(e,t)
\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\

These might help.

John

2009/1/17 David Møller Hansen <da...@mollerhansen.com>:

[David Møller Hansen]

> These might help.

Thanks. They most definitely will. I'll take a look at it..

/David

[nad.el...@gmail.com]

Hello.

On 17 Jan, 14:52, David Møller Hansen <da...@mollerhansen.com> wrote:
> > I found that she had emailed the code to me directly after the Sage
> > meeting. So I have asked her if I can post it.
>
> I've read the code and I pretty much agree with her, I'm just
> concerned about her line function, she returns the value 1 in the case
> where P_1 or P_2 both equal O but I would think that the line would
> have value x(P_1) - x(Q) when P_2 = O and P_1 \neq O.
>
> But she do not divide into lin. dep. and lin. indep. cases when she
> compute e_n = ((-1)^n)*(f_n(P,Q)/f_n(Q,P)).

I made this durong the coding sprint days in Nancy, and the code is
not proper. Some lines could be improved or forgetted.

I consider that during a pairing between P and Q of the same order two
cases can occuried.

P and Q are independant and then the line will never be zero, the
result is computed with the Miller algorithm.

Or P and Q are non independant, then the pairing computation will be
one and the line evaluation at point Q can be zero or not. If at a
moment the evaluation line is zero then the algorithme return 1 and
can finish at this moment.
If the evaluation is never zero, then the Miller algorithm works.

I hope my explainations are understandable.


Nadia.

[David Møller Hansen]

> P and Q are independant and then the line will never be zero, the
> result is computed with the Miller algorithm.

What about (when in this case) when P1 is zero and P2 is not zero,
shouldn't the line evaluate to Q[0]-P2[0] ?

/David

On Jan 19, 12:59 pm, "nad.elmra...@gmail.com" <nad.elmra...@gmail.com>
wrote:

[nad.el...@gmail.com]

On 24 Jan, 01:11, David Møller Hansen <da...@mollerhansen.com> wrote:
> > P and Q are independant and then the line will never be zero, the
> > result is computed with the Miller algorithm.
>
> What about (when in this case) when P1 is zero and P2 is not zero,
> shouldn't the line evaluate to  Q[0]-P2[0] ?
>
>

Yes it should be Q[0]-P2[0]. I made the program considering only
cryptographic cases, and then the case P1 is zero and P2 is not zero
happend at the last iteration and does not influence the result.

For a pairing in general, this case must be take in consideration.

Nadia.

[David Møller Hansen]

Thanks for your quick respond,
I guess that the only thing to do then is to catch the cases where the
line evaluates to zero, and return 1.

/David

On Jan 24, 3:32 pm, "nad.elmra...@gmail.com" <nad.elmra...@gmail.com>
wrote:

[John Cremona]

Dear Dan,

I'm CC-ing this to sage-nt which is the group where number
theory-related things in Sage are discussed.

It would be great to have good support for isogenies in Sage. This is
not at all limited to finite fields.

Velu's formulas are fine as far as they go, but there are other things
you should look at too. David Kohel's thesis is one place where
better formulas are obtained which do not involve using the
coordinates of the points in the kernel (that's an advantage since
these coordinates are in general in an extension field even when the
subgroup is rational). So functions to construct isogenies from a
given kernel would be better vased on that. (David was responsible
for Magma's very useful function IsogenyFromKernel which uses this).

A second useful thing to have would be over more general fields, say
over number fields: given a curve E, give me all the curves isogenous
to it (up to isomorphism) together with all the isogenies etc. Sage
can do this in part over Q only by calling my C++ code (or possibly my
similar gp code, I forget). Magma again does a good job, over number
fields, the code there being written by Mark Watkins. Some of the
formulas are in a preprint by Mark and me which I could send you if
you cannot find it.

Thirdly, and of interest in cryptographic applications: given two
elliptic curves over F_q with the same number of points, construct the
isogeny between them. There's a quite recent paper by Morain and
others showing how that can be done very efficiently using power
series to represent the rational functions. Doing that would again be
interesting, and would require implementation of fast algorithms for
power series -- I don't know how good Sage is at that yet.

There is a lot to do here -- how long have you got?! I am planning an
application to have an undergraduate student work on something for 6
weeks in the summer, and I had thought of doing some of these things,
so I would like to keep up with what you and others might be planning.

John

2009/1/24 Dan Shumow <shu...@gmail.com>:
> Hello Dr Cremona,
>
> I am a MS Student at the University of Washington. Presently, I am
> working on a Master's Thesis on Computing Isogenies of Elliptic Curves
> over finite fields. I was planning on writing up examples of Velu's
> formula, as well as some pairing stuff in Sage. However, it has
> recently come to my attention that this isn't supported in Sage, so I
> was thinking I would implement this as part of my thesis.
>
> So I would like to be involved in this:

>> Or we could also have a version for the phi-Weil pairing where phi is
>> an isogeny, and P and Q are on different though phi-isogenous curves.
>> I suspect that this case should wait, given that isogenies are not at
>> all implemented in Sage yet.
>

> I am presently translating the original Velu's formula paper, and I
> will start coding in a few days. Any thoughts/suggestions about how
> to implement isogenies in Sage would be greatly appreciated.
>
> Thanks,
> Dan

[Dan Shumow]

Dr Cremona,

Thanks for the prompt response and the suggestions. I'll start w/
Velu's formulas, and move onto David Kohel's thesis. I am very
interested in the third point about the cryptographic application. I
hadn't heard of that result, could you please send a pointer, or the
title? Although, I know somewhat about the random walks on isogeny
graph algorithms for the similar sort of thing (I used to work at MSR
and had some exposure to R. Venkatesan.)

In general, my main interest in isogenies is their application to
cryptography (Koblitz is my thesis adviser.)

I am less interested in isogenies of ECs over number fields, although
it was my impression that Velu's formulas work over any field
(although, like I said, I haven't finished translating / reading the
paper yet, so if I am wrong about this, please set me straight.) My
thinking was to write the general case code. Then investigate
formulas for the specific cases (like David Kohel's thesis) I will
look for your formulas. If I can't find that, I'll let you know.

I am interested in implementing a general phi-Weil pairing, that takes
an isogeny object, and I had been kicking around this idea in my own
head, you mentioning that it is a good thing to have has motiviated me
to try to include that as well.

As for the time frame. I want to be done w/ my thesis in June.
However, as you stated, there is plenty of work to be done here. And
I, of course, would continue to be involved (although depending on
what work I am doing at the time I don't know what sort of development
I can do in the summer.)

Thanks,
Dan

[David Møller Hansen]

> How general do you intend to make this? We could have P.weil_pairing
> (Q) defined whenever P and Q both had finite order, the result being a
> d'th root of unity where d = gcd(P.order(), Q.order()), with an
> exception being raised if either point has infinite order. The result
> should be in the common field of definiton of the curve on which both
> P and Q lie (they must lie on the same curve).

John, when you say common field of definition, are you then implying
that input P1, P2 where

P1\in E(F_2^7) and P2\in E(F_2^28) should be possible? I think this
will be a bit to heavy to have point coercing (can you say that)
happening beside the Miller algorithm in the pairing.

Or, did you mean that the result simply should be in F_2^28 for the
above when we pre coerce P1 into E(F_2^7) before pairing with
something in E(2_^28)?

/David

On Jan 11, 8:51 pm, John Cremona <John.Crem...@gmail.com> wrote:

[David Kohel]

Dear Dan,

> Thanks for the prompt response and the suggestions.  I'll start w/
> Velu's formulas, and move onto David Kohel's thesis.  

The point of the "explicit isogenies" chapter of my thesis is to
descend
Velu's formulas to the field of definition of the kernel subgroup.
The
formulas of Velu require the extension field over which the points of
the kernel subgroup split. I would suggest reading the article of
Velu
and my thesis chapter together (the latter is only a combinatorial
manipulation of Velu's identities and is thus elementary).

Best,

David

[John Cremona]

2009/1/24 David Møller Hansen <da...@mollerhansen.com>:

>
>> How general do you intend to make this? We could have P.weil_pairing
>> (Q) defined whenever P and Q both had finite order, the result being a
>> d'th root of unity where d = gcd(P.order(), Q.order()), with an
>> exception being raised if either point has infinite order. The result
>> should be in the common field of definiton of the curve on which both
>> P and Q lie (they must lie on the same curve).
>
> John, when you say common field of definition, are you then implying
> that input P1, P2 where
>
> P1\in E(F_2^7) and P2\in E(F_2^28) should be possible? I think this
> will be a bit to heavy to have point coercing (can you say that)
> happening beside the Miller algorithm in the pairing.
>
> Or, did you mean that the result simply should be in F_2^28 for the
> above when we pre coerce P1 into E(F_2^7) before pairing with
> something in E(2_^28)?

I mean the latter (assuming you meant to write "coercing Pi into
E(F_2^28)). But I'm not sure what you mean by the former! There is
no difference mathematically.

John

[David Møller Hansen]

> I mean the latter (assuming you meant to write "coercing Pi into
> E(F_2^28)). But I'm not sure what you mean by the former! There is
> no difference mathematically.

No only difference is the programming and the requirement on the
input.
Sorry about the confusing question, I understood the outcome.

Thanks.

/David

[David Møller Hansen]

> Excellent: will you submit a patch to ell_point.py?

Patch is submitted. For now I just added the simple version which
requires both P1 and P2 to be in E[n].
I have not included special cases n=2,3,4 yet. Since I couldn't come
up examples to test them on and to check if they are necessary.

/David

[John Cremona]

Where is your patch? There is nothing posted at #4964 but it has been
closed (which should only be done by a release manager).

The right procedure is to upload the patch to the tiket, mark the
ticket as "with patch, needs review", ,optionally prod a likely person
to review it, and wait.

John

2009/1/25 David Møller Hansen <da...@mollerhansen.com>:

[David Møller Hansen]

Sorry I thought the commit uploaded the patch automatically. I just
went out, writing on my phone. Could you reopen the ticket? Then I'll
do it right when I get back to my desk today. Sorry about the error.

/David

[John Cremona]

2009/1/25 David Møller Hansen <da...@mollerhansen.com>:
>

> Sorry I thought the commit uploaded the patch automatically. I just
> went out, writing on my phone. Could you reopen the ticket? Then I'll
> do it right when I get back to my desk today. Sorry about the error.

No problem I have reopened the ticket. Committing your changes only
affects your own private Sage build. What I would do next is (from
within Sage) hg_sage.export("tip") which puts a file called nnn.patch
into te current directory. Rename it trac_4964.patch (say) and then
go to the ticket, click on "Attach file", select your patch file and
that's it. It's also helpful to add a comment saying exactly which
version it is a patch against -- especially at times like right now
when there's a new alpha out every time you blink!

John

[David Møller Hansen]

Finally the patch is uploaded correctly now. Just have a question
about marking the ticket.

> The right procedure is to upload the patch to the tiket, mark the
> ticket as "with patch, needs review", ,optionally prod a likely person
> to review it, and wait.

How do I mark it like you say in the above - I only see the action to
resolve it as fixed, but that closed it last time I did it.

By the way, thanks for all the support.

/David

[Alex Ghitza]

Just edit the summary of the ticket and prepend [with patch, needs review] to whatever the summary is now.

Alex

--
Alex Ghitza -- Lecturer in Mathematics -- The University of Melbourne -- Australia -- http://www.ms.unimelb.edu.au/~aghitza/

[David Møller Hansen]

Great! Thank you - think it is correct now.

So if anyone want review some Weil pairing code, it's open for bids on
trac.

/David

[Dan Shumow]

Dr Kohel,

Thank you very much for the info. I actually downloaded your thesis
several months ago, and read about some of the basic theories of
isogenies in it. It was very helpful. However, I did not read the
"explicit isogenies" chapter (I was just following up on references my
adviser gave me, and not reading the whole work.) I will definitely
take your suggestion, and read that chapter and velu side by side.

Thanks,
Dan

[John Cremona]

We need someone to take a look at ticket #4964 (implementing Weil
pairings). David Hansen did the implementation and patch, I reviewed
it and added a little extra, so we would like a third party to take a
look.

John

2009/1/25 Alex Ghitza <agh...@gmail.com>:

[nad.el...@gmail.com]

Hello.

I would be very happy to help you. But I do not where finding the
ticket#4964, could you help me ?

Thank you.

Nadia.

[Alex Ghitza]

Try

http://trac.sagemath.org/sage_trac/ticket/4964

[nad.el...@gmail.com]

Thank you Alex.

I just read the three patch, and they seem correct.

I do not try them, I will try to test the bilinearity.

With the Miller algorithm, it would be quite easy to have the Tate,
Ate and Twisted Ate pairings ?

Nadia.

[nad.el...@gmail.com]