[curves] libsecp256k1's novel(?) ECDSA verification optimization

[Gregory Maxwell]

On Wed, Mar 23, 2016 at 12:16 PM, Brian Smith <brian at 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).