On Wed, Mar 23, 2016 at 12:16 PM, Brian Smith <br...@briansmith.org> wrote: > Hi, > > [I am not sure if boring topics like ECDSA are appropriate for this list. I > hope this is interesting enough.]
It's no less useful for Schnorr (just even more obvious there), and in that case it permits a verification to be implemented completely without any modular inversion. For libsecp256k1 it's roughly a 4% speedup; performance would depend on how optimized everything else is compared to your modular inversion, of course. As far as I know the optimization is novel, though it seems too obvious to be new... (unless it's broken, of course, :-) ) As noted by Rene Struik the implementation must check all conditions that result from modular reduction, and as noted by Ruggero SUSELLA, ours does. Libsecp256k1 also includes test vectors that try the conditions/decisions of these branches, so if any were omitted the tests would fail. I would encourage other implementers who adopted this optimization to also include specific tests for it passing and failing each branch-- to avoid a later developer optimizing away an 'impossible' case. Though these cases are 'rare', the triggering conditions can be generated by backwards computing public keys from constructed signatures where R.x is a very high value. For ECDSA the approach is one that loses its utility with larger trace/co-factor; as there end up being many cases to check; so it may not be worthwhile for some curves. Going outside of your likely domain of interest-- One limitation we have had with it is that for our future applications we want batchable schnorr signatures which behave identically in batch and non-batch verifiers. Batching require r's sign be provided or specified. If this trick were used naively in the non-batch verifier then it would admit signatures that the batch verifier would reject (ones with an incorrect sign)-- violating our consistency requirement. If the sign is checked either of the obvious ways (using either a sqrt and the curve equation on r.x, or a modular inverse to project R.y back to affine (which could have been batched with the projection of R.x)) then the performance gain from this improvement is lost. We do have a cute trick to solve this now, whos efficiency specific to some fields (basically by specifying the signer choose R.y to be a quadratic residue the sign check can be done by the non-batch verifier in the protective coordinates with just a legendre symbol). _______________________________________________ Curves mailing list Curves@moderncrypto.org https://moderncrypto.org/mailman/listinfo/curves