3

In the BIP by Pieter Wuille it is told that the key prefixed version of Schnorr signature is needed when the scheme is used in combination with BIP32's unhardened derivation. Could someone provide an example showing this necessity? I couldn't figure out one by myself.

Always in the BIP, when coming to batch validation we can see that there is the need for random number generation. Again, could someone provide an example showing that the simpler version is insecure? I found out that the reason is the so called "cancellation attack". I would like to figure out how it can be exploited.

Thanks in advance for your answers!

1 Answer 1

4

A schnorr signature, without key prefixing, is a tuple {pubkey (P), message (m), R, s} where the equation R == sG + H(R||m)P holds.

Now, assume you have pubkeys P and P2 who's discrete logs differ by c which is known to me, as is the case for non-hardened BIP 32 when I know the extended pubkey (P2 == P + cG). If I know a signature by pubkey P of message m, I can use it to forge a signature of m by pubkey P2: {P2, m, R, s - H(R||m)c} because if you write out the relation for P2 and then express it in terms of the relation for the first signature, that's what you get.

For batching: The task there is we have two to n equations of the form R_n = s_nG + h_nP_n, we could naively batch verify by first rewrite them as 0 = sum(s_n)G + sum(h_nP_n) - sum(R_n) and then using an efficient multiexp to compute the big product-sum. E.g. if we want to make {P1, m1, R1, s1} hold we can add to the batch {-P1, m1, R1, -s1} so now the errors cancel.

To resolve this, the verifier should delinearize the equations by multiplying each one by an attacker unknown value which makes them unable to cancel with odds better than chance. This can be done without hurting efficiency much by substituting it into the scalars in the multiexp.

For an even simpler example: consider the batch verification where the attacker knows all valid signatures. The attacker can simply shuffle the s values between signatures in the batch. Without delinearization the batch would obviously still pass (as the naive sum doesn't care about the order of s values), yet the signatures would all be invalid.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.