Jacobi quartic form curves

89 views
Skip to first unread message

Wei Dai

unread,
Apr 16, 2009, 4:31:11 PM4/16/09
to crypto-op...@googlegroups.com
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

unread,
Apr 21, 2009, 1:33:43 AM4/21/09
to crypto-op...@googlegroups.com
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

signature.asc

hisil....@gmail.com

unread,
Apr 21, 2009, 3:07:27 AM4/21/09
to crypto-optimization

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

unread,
Apr 21, 2009, 6:21:34 AM4/21/09
to crypto-op...@googlegroups.com
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

unread,
Apr 24, 2009, 10:52:38 AM4/24/09
to crypto-optimization
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

unread,
May 1, 2009, 7:31:55 AM5/1/09
to crypto-optimization
> 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.


Reply all
Reply to author
Forward
0 new messages