[curves] New curve25519/ed25519 library

[Mike Hamburg]

Hi Mehdi,

I think your "folding" trick has been invented and re-invented many
times.  I came up with it in 2012, and thought it should be called
"combs".  I Googled the term, and found that Pippenger invented it in
1979. Lim and Lee reinvented it in 1994. Hankerson-Menezes-Vanstone
improved it in 2004 (by using multiple tables), as did Hedabou (by using
signed all-bits-set binary); Feng et al published a different version in
2006 (signed-MSB-set).  The first Ed25519 implementation used a less
efficient, non-combed variant of the same technique.

Some of the variants are patented, too, but I think your variant is
similar to Lim-Lee and so should probably be out of patent by now.

I think the best variant these days is to combine the 2004 techniques:
multiple combs, signed-all-bits-set.  It's simpler than signed-MSB-set,
and I think it's the fastest once you have the table.  The table is
slightly slower to compute than signed-MSB-set, which makes that
algorithm better in a few limited circumstances, but SMSBS is also
patented (by Microsoft) and SABS is unpatented to the best of my knowledge.

You're right that fixed-point techniques can be useful for verification
and not just signing.  For example, in a vehicle-to-vehicle setting, you
will see many signed messages from each car going the same direction as
you.  Verification latency is important, so precomputing a small table
on another core may be worthwhile if memory permits.  A small table can
be worthwhile even for only 2 signatures, and a larger one for 3.

-- Mike

On 06/30/2015 10:26 AM, Peter Schwabe wrote:
> Mehdi Sotoodeh <mehdisotoodeh at gmail.com> wrote:
>
> Dear Mehdi,
>
>> I would like to introduce a remarkable implementation of x25519 and ed25519
>> library. The sources are hosted at: https://github.com/msotoodeh/curve25519
>>
>> The code is experimental but rather stable. It is compact, portable
>> and uses simple design logic.  On the security front, it employs
>> several measures for side-channel security.
> I only took a quick look at the software, but two things immediately
> caught my eye. 
>
> The first aspect is that the Curve25519 implementation uses secretly
> indexed memory access which is a possible source for timing attacks.
> State-of-the-art Curve25519 implementations avoid this by using
> constant-time conditional swaps.
> Similar statements apply to the table lookup in the fixed-basepoint
> scalar multiplication, but those would be much more expensive to
> protect.
>
>> But the most remarkable feature is speed. This library sets new speed
>> records. It uses a new technique I call it FOLDING for achieving this goal.
>> FOLDING chops the scalar multiplier into n pieces (or folds) and operates
>> on the folds simultaneously reducing number of point operations by a factor
>> of 4 or 8. For example, ed25519 signature takes 31 point doubling and 31
>> point additions.
> The second thing is: It's great to hear about new speed records!
> Are you planning to support the SUPERCOP API and submit to eBATS so that
> the software can be publicly benchmarked on a large bunch of computers?
> My understanding is that the technique that you call folding is only
> efficient for signing; the verification part needs a precomputation
> which is just way too expensive: it needs 384 point doublings! You will
> probably answer that the ed25519_Verify_Init needs to be done just once
> for many verifications, but then a huge expanded public key is sitting
> around in memory and if I'm not totally mistaken, a sliding-window
> method would still be faster. 
>
> Best regards,
>
> Peter
>
>
> _______________________________________________
> Curves mailing list
> Curves at moderncrypto.org
> https://moderncrypto.org/mailman/listinfo/curves

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://moderncrypto.org/mail-archive/curves/attachments/20150630/ec24ee60/attachment.html>