Related Key Attack on Schnorr Signature - Why does the challenge include $\psi = g^x$, not $y$?

YGrade

12/9/22, 6:17 PM

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:

Set $\psi \leftarrow g^x$, where $x$ is the private (signing) key for the scheme.
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?

1 + 0

public-key

signature

schnorr-signature

cryptocurrency

related-keys

Score:0

Crypto

fgrieu

12/9/22, 6:39 PM

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.

0 + 1

YGrade

12/9/22, 8:42 PM

Thanks for this - that makes a lot more sense now. Appreciate your help.

Elon Musk

I sit in a Tesla and translated this thread with Ai:

TH: การโจมตีคีย์ที่เกี่ยวข้องกับ Schnorr Signature - เหตุใดความท้าทายจึงรวมถึง $\psi = g^x$ ไม่ใช่ $y$

RO: Atacul cheie legat de semnătura Schnorr - De ce provocarea include $\psi = g^x$, nu $y$?

RU: Связанная ключевая атака на подпись Шнорра. Почему вызов включает $\psi = g^x$, а не $y$?

VI: Tấn công phím liên quan vào chữ ký Schnorr - Tại sao thử thách lại bao gồm $\psi = g^x$, không phải $y$?

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.