I thought I understood the Generalized Birthday Attack (GBA), but due to ongoing discussions on other topics Is this distributed random oracle scheme safe? I'm not certain anymore.

Defining $M_i$ as EC share points in a $(t, n)$-yhreshold scheme for the corresponding nonce $m$ used in a Schnorr signature. I believe the general principle begins with a rogue key attack, forcing a certain nonce value $M$ from $M_0 + \sum_{i=1}^t M_i^* = M$. Being $M_i^*$ the values from the attacker and $M_0$ the value of the honest node.

The attacker is able to force $j$ nuber of $M_j$ values an signatures, where the k-sum is applied.

The common solution (such as the ones used in threshold signatures) is to apply a commitment round for the $M_i$ values. From this principle, if a honest client hides $M_0$ from the attacker, this should be enough to avoid the rogue key computation, preventing the problem from the beginning. This may be feasible in practice, if the client participates in the signature scheme and it's correctly authenticated. Only by compromising the authentication can we get $M_0$, but by then it's completely redundant to use the GBA since we already have the power to request for valid signatures.

Also, is it possible to output a signature for a public key $P_a$ by applying the GBA in values from a different set of a key $P_b$, where $P_a \neq P_b$? Meaning, can I attack signatures generated from other clients?

If such constraints are possible, I can apply those principles without raising questions about the GBA anymore.

  • $\begingroup$ Terribly written question. Please define these terms, what is $M_i^{\ast}$, $M_0,$ and $M$. What is the goal. If there are related questions, link them. $\endgroup$ – kodlu Mar 11 '20 at 0:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.