<html><head><meta http-equiv="Content-Type" content="text/html charset=windows-1252"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class=""><div class="">I should add to this that I haven’t actually seen a complete comb implementation for Curve25519 before, though there might be one somewhere. I think Donna (including Floodyberry’s Donna fork) uses the older windowed technique. So if you make a nicely tuned implementation, you will be the first. I’m working on one as well, but it uses Decaf so it won’t be directly compatible with curve25519.</div><div class=""><br class=""></div><div class="">To tune your comb implementation, here are a few ideas:</div><div class=""><br class=""></div><div class="">1) As Peter said, you should probably use constant-time lookups for signing, though it isn’t necessary for verification. This will limit you to a smaller table.</div><div class=""><br class=""></div><div class="">2) Signed binary uses half the table space vs unsigned binary, and also is half as expensive if you’re using constant-time lookups. You can convert a scalar to signed binary by adding a certain constant (2^width-1 IIRC) and halving mod the curve order.</div><div class=""><br class=""></div><div class="">3) Using multiple tables (so the inner loop is double; add; add; add) lets you reduce the number of doubles without making the tables too wide.</div><div class=""><br class=""></div><div class="">4) For any given size, there's a tradeoff between more tables and bigger tables. You can optimize that tradeoff with a simple script or spreadsheet.</div><div class=""><br class=""></div><div class="">Cheers,</div><div class="">— Mike</div><br class=""><div><blockquote type="cite" class=""><div class="">On Jun 30, 2015, at 10:56 AM, Mike Hamburg <<a href="mailto:mike@shiftleft.org" class="">mike@shiftleft.org</a>> wrote:</div><br class="Apple-interchange-newline"><div class="">
<meta content="text/html; charset=windows-1252" http-equiv="Content-Type" class="">
<div bgcolor="#FFFFFF" text="#000000" class="">
Hi Mehdi,<br class="">
<br class="">
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.<br class="">
<br class="">
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.<br class="">
<br class="">
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.<br class="">
<br class="">
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.<br class="">
<br class="">
-- Mike<br class="">
<br class="">
<div class="moz-cite-prefix">On 06/30/2015 10:26 AM, Peter Schwabe
wrote:<br class="">
</div>
<blockquote cite="mid:20150630172637.GC19202@tyrion" type="cite" class="">
<pre wrap="" class="">Mehdi Sotoodeh <a class="moz-txt-link-rfc2396E" href="mailto:mehdisotoodeh@gmail.com"><mehdisotoodeh@gmail.com></a> wrote:
Dear Mehdi,
</pre>
<blockquote type="cite" class="">
<pre wrap="" class="">I would like to introduce a remarkable implementation of x25519 and ed25519
library. The sources are hosted at: <a class="moz-txt-link-freetext" href="https://github.com/msotoodeh/curve25519">https://github.com/msotoodeh/curve25519</a>
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.
</pre>
</blockquote>
<pre wrap="" class="">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.
</pre>
<blockquote type="cite" class="">
<pre wrap="" class="">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.
</pre>
</blockquote>
<pre wrap="" class="">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
</pre>
<br class="">
<fieldset class="mimeAttachmentHeader"></fieldset>
<br class="">
<pre wrap="" class="">_______________________________________________
Curves mailing list
<a class="moz-txt-link-abbreviated" href="mailto:Curves@moderncrypto.org">Curves@moderncrypto.org</a>
<a class="moz-txt-link-freetext" href="https://moderncrypto.org/mailman/listinfo/curves">https://moderncrypto.org/mailman/listinfo/curves</a>
</pre>
</blockquote>
<br class="">
</div>
_______________________________________________<br class="">Curves mailing list<br class=""><a href="mailto:Curves@moderncrypto.org" class="">Curves@moderncrypto.org</a><br class="">https://moderncrypto.org/mailman/listinfo/curves<br class=""></div></blockquote></div><br class=""></body></html>