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 <rocon...@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. > > >

_______________________________________________ bitcoin-dev mailing list bitcoin-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev