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 <[email protected]> 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 > [email protected] > https://moderncrypto.org/mailman/listinfo/curves
_______________________________________________ Curves mailing list [email protected] https://moderncrypto.org/mailman/listinfo/curves
