The paper "Fast Secure Two-Party ECDSA Signing" by Yehuda Lindell describes a system in which two parties, $P_1$ (with 1/2 of a share of a long-term ECDSA signing key $x_1$) and $P_2$ (with the other 1/2 share, $x_2$), cooperate in order to produce an ECDSA signature, $P_1$ being the party that actually outputs the final signature.

In Section 3.2, describing the process for distributed signing, it is said that a hypothetical attack by $P_2$ implies sending a malicious message such that if $x_1 \bmod 2 = 0$ then the final signature is incorrect (and hence $P_1$ will not output a signature), and if $x_1 \bmod 2 = 1$, then the final signature is correct (and hence $P_1$ will output a signature). The author refers then to the security proof for details on how to handle this.

If I am not mistaken, it is in Section 4.1, pages 20-22, where this is addressed (there is an alternative security proof in Section 5, but I am focusing on the one in Section 4). In this section, security is proven by reducing to the security of ECDSA (i.e., if we have an attacker $A$ that breaks the 2-party ECDSA, then we can build an attacker that breaks ECDSA). Specifically, for the matter at hand, the strategy is to have the simulator simulate $P_1$ aborting at some random point. This makes the simulated view be indistinguishable to the real view with non-negligible probability, so we can use $A$ to break the 2-party ECDSA, then use this to break ECDSA, and so on.

Now, my doubt is: how does this demonstrate that a malicious $P_2$ is prevented from learning the LSB of $x_1$ if the hypothetical attack mentioned in Section 3.2 were possible. Or does this imply that, in practice, we would actually need to force $P_1$ to abort randomly? In that case, is this realistic in practice?


1 Answer 1


In real life, $P_1$ of course does not abort randomly; this would make no sense. The idea is as follows. Assume that a cheating $P_2$ can forge a signature with probability $\epsilon$ when interacting to obtain $p(n)$ signatures are signed with the system. Now, if $P_2$ cheats then there is a first place where $P_1$ aborts. An adversary for ECDSA can simulate everything and guess where this first abort happens and will be correct with probability $1/p(n)$. This implies that the adversary for ECDSA can forge a signature with probability $\epsilon/p(n)$. Since ECDSA is assumed to be secure, this means that $\epsilon$ must be negligible.

  • $\begingroup$ I see now. I thought the aborting strategy was only needed to prove indistinguishability of the simulation. Thanks! $\endgroup$
    – Ginswich
    Commented Dec 28, 2018 at 8:54

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.