0
$\begingroup$

The original Schnorr signature scheme suffers from a Related Key Attack (RKA) as described by Morita et al. The authors of this paper then suggest a modification to the signature algorithm to prevent a RKA as follows:

  1. Set $\psi \leftarrow g^x$, where $x$ is the private (signing) key for the scheme.
  2. Set the challenge hash to be $h \leftarrow H(M || r || \psi)$.

The second step above differs from the original Schnorr scheme (here) that only requires $h \leftarrow H(r || M)$.

This modification makes sense, however the paper by Morita et al. says (on page 9):

"Note that the second step of the signing algorithm, computation of $\psi \leftarrow g^x$, should not be altered to simply use the verification key $y$ as $\psi$."

The authors don't explain why $y$ (the public / verification key) cannot be used in place of $\psi$, even though are exactly the same value - is there a reason for this?

What makes this even more confusing is that with Schnorr being added to Bitcoin in the Taproot soft fork, Bitcoin Core developers have written their own implementation for Schnorr signatures (as described in BIP340), including the mitigations for RKA. However, in BIP340, they have decided to use $y$ in the challenge hash over $\psi$, going against the recommendation from earlier.

Is this implementation wrong?

$\endgroup$

1 Answer 1

0
$\begingroup$

The authors don't explain why $y$ (the public / verification key) cannot be used in place of $\psi$, even though they are exactly the same value. Is there a reason for this?

Yes. The idea is that an alteration of the private key $x$ into a related $x'$ will change the $\psi\leftarrow g^{x'}$ recomputed at time of signature into something different from $y=g^x$ originally computed, with $\psi$ entering the hash thus protecting from the related-key attack.

Bitcoin Core developers (..) have decided to use $y$ in the challenge hash over $\psi$.

That's not how I read the spec. On the contrary signature seems to recompute $d'$ (which I read as acting as $x'$) then $P$ (which I read as acting like $\psi$) from the currently assumed private key. And implementation variations of that, if any, are off-topic.

This is not to be construed as en endorsement of bitcoin or any fork or implementation thereof. I personally consider the whole stuff as an insult to humanity.

$\endgroup$
1
  • $\begingroup$ Thanks for this - that makes a lot more sense now. Appreciate your help. $\endgroup$
    – YGrade
    Aug 9, 2021 at 20:42

Your Answer

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

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