[curves] How close is Mike's Ed448 to being production-ready?
nicholas at nicholaswilson.me.uk
Mon Sep 1 11:35:14 PDT 2014
Thanks for the thorough reply! I hope you've been feeling better over
On 30 August 2014 01:51, Michael Hamburg <mike at shiftleft.org> wrote:
> I really should write a ref version.
I'm taking the arch_32 code as the baseline at the moment, it only
needs a bit of tweaking to compile on various platforms. I'm running
tests at the moment on SPARC, PA-RISC, Itanium, and POWER because I
guess the code hasn't had an outing on those arches yet! Once I get
some results, I'll report back. Are there any unittests or other
things I could run for you usefully there? I'm using GCC, clang, MSVC,
and xlc at the moment.
> Yeah, the CPU-specific stuff is scary. Sorry about that. In addition to a garbage-free /ref/, I should also unify the existing copy-pasta as much as possible. Eg functions that differ only in limb sizes, temporary names and calls to p448_bias().
> The asm widemul intrinsics should be easy to remove.
> Most of the __attributes__ are there to support static analysis or strong warnings, or just to be as strong as possible with the inliner, and can be removed. Eg __attribute__((unused)) for header functions is there for -Wunused-function.
> One of the less portable things in the code is the vector intrinsic stuff, which I think is specific to GCC and Clang. It should be possible to just remove everything that depends on SSE, though. If your compiler’s vectorizer actually works (unlike, say, clang’s), then this shouldn’t even be a big perf regression.
I'll be playing around with it this week hopefully, schedule allowing,
and work out whether there are any cheap wins for the adding support
for the arches we use here. If the arch_32 code runs at acceptable
performance, that'll be good news.
> Unfortunately, there isn’t a “preferred” serialization, and from discussions here and on CFRG, I’m concerned that there won’t be for a while. Half the guys there want short Weierstrass for everything, and the other half don’t want to put new wine in old wineskins.
> ... There’s a follow-on problem to this, too. The Ed448 point format intentionally only represents the 2q-order subgroup (including the identity but not the point of order 2; and the *non*-2q’ subset of the twist if you don’t do the on-the-curve check). This means that any protocol requiring cofactor removal can multiply by 2, so long as it’s checked that the point is indeed on the curve. (There’s something about a Huff curve with group structure 2*2*q in here, but I don’t remember exactly how it works out.) Anyway, if the point format changes and can represent the whole group, you’ll have to multiply by 4.
That's a shame, but what I suspected from the posts I've been reading.
If we do use it our product, we could well send the serialised points
with the longer format, to make sure we don't get stuck doing
something unconventional. I need to brush up on my algebra to be able
to follow the details for myself.
All the best,
More information about the Curves