Jacobi quartic form curves

[Wei Dai]

I've been updating myself on the latest elliptic curve techniques, and found
a March 2009 update of http://eprint.iacr.org/2007/441, which claims (based
on theoretical calculations) that elliptic curve scalar multiplication
should be fastest in Jacobi quartic form. Looking at the latest eBATS
results, the fastest curves that have been implemented are gls1271 and
curve25519, with curve25519 being slightly behind. Switching from
curve25519's Montgomery form to Jacobi quartic form should cause a speedup,
plus curve25519's x64 assembly implementation (from mpfq) can be optimized a
bit more. These improvements together seem to have a good chance of bringing
a Jacobi quartic variant of curve25519 to the top. Before I try to implement
this, has anyone else read that paper, or know of faster techniques that I
should try instead?

[Peter Schwabe]

you might want to look into
http://cr.yp.to/antiforgery/efd-20071204.pdf, this paper suggests
Inverted Edwards coordinates as the fastest way to implement EC
arithmetic.
Some weeks ago Mike Scott submitted a new version of gls1271 (using
Edwards coordinates)... so perhaps wait for benchmarking of this
software?

Cheers,

Peter

[hisil....@gmail.com]

On Apr 17, 6:31 am, "Wei Dai" <wei...@weidai.com> wrote:
> I've been updating myself on the latest elliptic curve techniques, and found

> a March 2009 update ofhttp://eprint.iacr.org/2007/441, which claims (based

> on theoretical calculations) that elliptic curve scalar multiplication
> should be fastest in Jacobi quartic form. Looking at the latest eBATS
> results, the fastest curves that have been implemented are gls1271 and
> curve25519, with curve25519 being slightly behind. Switching from
> curve25519's Montgomery form to Jacobi quartic form should cause a speedup,
> plus curve25519's x64 assembly implementation (from mpfq) can be optimized a
> bit more. These improvements together seem to have a good chance of bringing
> a Jacobi quartic variant of curve25519 to the top. Before I try to implement
> this, has anyone else read that paper, or know of faster techniques that I
> should try instead?

Hi Wei,

The last sentence of Section 2.3 of

http://eprint.iacr.org/2007/441

says

"We should note here that our more recent work (Hisil
et al. 2008) which was published before this work,
further improves these operation counts on twisted
Edwards curves."

So please have look at

http://eprint.iacr.org/2008/522.pdf

;=)

Cheers,
Huseyin Hisil.

[Michael Scott]

The whole situation regarding the best parameterisation to use appears to still be in a state of flux, with new results appearing regularly. So maybe its still too soon to say.

 

I personally prefer a projective representation with just three coordinates (X,Y,Z), and with this constraint inverted Edwards seems hard to beat. There has surely got to be some significant overhead to handling up to 6 coordinates per point..

 

 

Mike Scott

[Wei Dai]

Huseyin Hisil wrote:
> So please have look at
>
> http://eprint.iacr.org/2008/522.pdf

Thanks for this pointer. Are you still working in this area? Do you think
further big improvements in explicit formulas are likely? I'm wondering if I
should pick a fast curve form now to include in Crypto++, or wait until
things settle down a bit more.

Has anyone tried to estimate a lower bound on the number of field operations
needed for a curve scalar multiplication?

[hisil....@gmail.com]

> Thanks for this pointer. Are you still working in this area? Do you think
> further big improvements in explicit formulas are likely?
> I'm wondering if I should pick a fast curve form now to include in Crypto++, or wait until
> things settle down a bit more.

Yes, I am still working on the topic.
I believe that there will be many more improvements in the future. I
hope, it never settles down ;=).
We have a new ACISP09 paper coming up for Jacobi quartics.

I have implemented both curves in Diffie-Hellman key exchange with
latest formulas, assembly optimizations, and lookup tables.
Twisted Edwards (a=-1) seems to be superior in performance.

> Has anyone tried to estimate a lower bound on the number of field operations
> needed for a curve scalar multiplication?

I do not know any results on this.

Regards,
Huseyin Hisil.