<html> <head> <meta content="text/html; charset=windows-1252" http-equiv="Content-Type"> </head> <body bgcolor="#FFFFFF" text="#000000"> 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 <div class="moz-cite-prefix">On 06/30/2015 10:26 AM, Peter Schwabe wrote: </div> <blockquote cite="mid:20150630172637.GC19202@tyrion" type="cite"> <pre wrap="">Mehdi Sotoodeh <a class="moz-txt-link-rfc2396E" href="mailto:mehdisotoodeh@gmail.com"><mehdisotoodeh@gmail.com></a> wrote: Dear Mehdi, </pre> <blockquote type="cite"> <pre wrap="">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=""> 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"> <pre wrap="">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=""> 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> <fieldset class="mimeAttachmentHeader"></fieldset> <pre wrap="">_______________________________________________ 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> </body> </html>