Over chat it has been pointed out to me that computing the non-quadratic residue is not the same cost as computing a quadratic residue. As pointed out in footnote 7 of the the proposed BIP, c^((p+1)/4) is always a quadratic residue and must be negated to find the non-quadratic residue.

In light of this, I revise my proposed change to make the verification equation

R + sG + eP = 0.

(by 0 in the equation above I mean the identity element for the (+) operation, which is the point at infinity.)

This equation is suitable for batch verification. This equation is clearly written as a linear combination that doesn't use negation. In most implementations, equality comparison tests are implemented by subtraction and a comparison with zero. By writing the verification equation this way, we clearly see that only the comparison with zero test is needed.

For single signature verification the check becomes, compute Q := sG + eP. Verify that Q isn't the point at infinity and Q.x = r. Verify that Q.y is *not* a quadratic residue. (While I was incorrect earlier about the costs of computing a non-residue, it is the case the *verifying* a value is a quadratic residue is the same cost as verifying a value is a non-residue.)

Effectively in my first email I was suggesting that the 'e' value in a signature be negated from the current BIP proposal. In this revision I am effectively suggesting that the 's' value in a signature should be the one that is negated instead.

On Sat, Aug 4, 2018 at 8:22 AM, Russell O'Connor <roconnor@blockstream.io> wrote:

I propose changing the verification equation from "Let R = sG - eP" to

Let R = sG + eP

This allows faster verification by avoiding negating a point (or a coefficient).

If, instead of directly following the literal verification specification, one is instead reconstructing R from r by finding a y coordinate that is a quadratic residue, under the existing scheme one would verify

sG - eP = R

which is effectively verifying

0 = sG - eP - R or 0 = R - sG + eP

Either way one needs to negate at least one point (or one coefficient) because of the opposite signs between sG and eP.

Under my proposed revised verification scheme, one would instead verify

0 = sG + eP + (-R).

While it seems that this requires negating R, it does not. Rather (-R) can be directly constructed from r by finding a y coordinate that is *not* a quadratic residue, which is precisely the same amount of work that construction R from r was.

In either verification procedure, changing the verification equation to my proposal removes one negation operation from the cost of doing verification.