Published Dec 16, 2020 9:45:38 AM
Introduction
Multi-party computation (MPC) uses secret inputs to arrive at an output such that the inputs are never revealed to the other parties involved in the calculation. In the context of Elliptic Curve Digital Signature Algorithm (ECDSA) the secret values are the private key, $w$, and the ephemeral secret value, $k$. Both these values are random integers less than a large prime $n$. It is therefore possible to generate a signature that is a function of several private key shares such that the private key is never combined in whole form.
This document will outline the main steps of the Gennaro and Goldfeder solution for implementing MPC over ECDSA signatures. This is a threshold solution but for this example we assume that there are two parties and that they have been provided with their respective keys in a trustless manner.
1.1 ECDSA
The ECDSA private key, $w$, and public key, $Q$, are generated as follows; \begin{equation*} \begin{split} w\in\mathbf{Z}_n \\ Q=wG \end{split} \end{equation*} where $\mathbf{Z}_n$ denotes integers modulo $n$, $G$ is a point on the secp256k1 elliptic curve used to generate the group and $wG$ is group multiplication. The signature over a message, $m$, has values $r$ and $s$ which are calculated as follows; \begin{equation*} \begin{split} k & \in\mathbf{Z}_n \\ (x,y) & =k^{-1}G \\ r & = x\text{ }\mathrm{mod}\text{ }n \\ z & =H(m) \\ s & =k(z+rw)\text{ }\mathrm{mod}\text{ }n \end{split} \end{equation*} where $(x,y)$ are the $x$ and $y$ coordinates of the point on the ecliptic curve and $H(m)$ is a hash to an integer.
Key setup
There is a series of steps that must be followed so that all parties can engage in the generation of a MPC threshold signature. For the purposes of this exercise we assume that Alice and Bob each have a share of the key that is required to form a valid signature. Alice's ECDSA private key, $w_A$, and public key, $Q_A$, are; \begin{equation*} \begin{split} w_A\in\mathbf{Z}_n \\ Q_A=w_AG \end{split} \end{equation*} Bob's ECDSA private key, $w_B$, and public key, $Q_B$, are; \begin{equation*} \begin{split} w_B\in\mathbf{Z}_n \\ Q_B=w_BG \end{split} \end{equation*} The complete ECDSA private key, $w$, is never generated. \begin{equation*} \begin{split} w = w_A + w_B \end{split} \end{equation*} The complete ECDSA public key, $Q$, can be calculated by each party sending their respective public key shares. \begin{equation*} \begin{split} Q & = Q_A + Q_B \\ & = (w_A + w_B)G \end{split} \end{equation*}
Distributed signature
As the keys are distributed among two parties, then the ECDSA protocol can be written as follows where $k_A$ is Alice's ephemeral secret value and $k_B$ is Bob's. \begin{equation*} \begin{split} k_A & \in\mathbf{Z}_n \\ k_B & \in\mathbf{Z}_n \\ (x,y) & = (k_A + k_B)^{-1}G \\ r & = x\text{ }\mathrm{mod}\text{ }n \\ z & = H(m) \\ s & = (k_A + k_B)(z+r(w_A + w_B))\text{ }\mathrm{mod}\text{ }n \\ s & = (k_A + k_B)z+r(k_A + k_B)(w_A + w_B)\text{ }\mathrm{mod}\text{ }n \end{split} \end{equation*} The end result will be that each party has the $r$ value and an additive share of $s$.
Multiplicative to Additive conversion
The two distributed values that are required are $(k_A + k_B)^{-1}G$ and $(k_A + k_B)(w_A + w_B)$. Note that $(k_A + k_B)^{-1}$ is never calculated on its own. Alice and Bob generate random integers $\gamma_A$ and $\gamma_B$ respectively to mask their $k$ values. What is calculated is $(k_A + k_b)(\gamma_A + \gamma_B)$ which is inverted and multiplied by a point $(\gamma_A + \gamma_B)G$ to remove the mask whilst still protecting $(k_A + k_B)$ due to the intractability of the discrete logarithm problem (see section:Calculate $r$) The product $(k_A + k_b)(\gamma_A + \gamma_B)$ can be expanded as follows; \begin{equation*} \begin{split} k\gamma & = (k_A + k_B)(\gamma_A{} + \gamma_B{}) \\ & = k_A\gamma_A + k_A\gamma_B + k_B\gamma_A + k_B\gamma_B \end{split} \end{equation*} Alice knows the term $k_A\gamma_A$ and Bob knows $k_B\gamma_B$. They both need to have additive shares of other terms i.e. $k_A\gamma_B$ and $k_B\gamma_A$.
The Multiplicative to Additive conversion (MtA) is required for this task. It converts multiplicative secret shares to additive secret shares. If Alice has value $a$ and Bob has value $b$ then the output of the MtA would be that Alice has the value $\alpha$ and Bob has $\beta$ such that they sum to the value $ab$. \begin{equation*} \begin{split} \delta & = ab \\ & = \alpha + \beta \end{split} \end{equation*} The Paillier Cryptosystem is used for this task. It is a public key cryptosystem that is homomorphic. This means that you can perform calculations on encrypted data.
For example; \begin{equation*} E(a) \cdot E(b)=E(a+b)\text{ }\mathrm{mod}\text{ }n^2 \end{equation*} and \begin{equation*} E(a)^c=E(ac)\text{ }\mathrm{mod}\text{ }n^2 \end{equation*} where $a,b,c\in\mathbf{Z}_n$. Figure 1.1 shows the protocol. In this diagram, $E_A$ means Paillier encryption with Alice's public key, and likewise $D_A$ means Paillier decryption. 
Figure 1.2 $ \sigma$ value generation using MtA
From Figure 1.2, Alice has additive share, $\sigma_A$, and Bob's has share, $\sigma_B$, which when added together sum to $\delta$; \begin{equation*} \begin{split} \delta & = \sigma_A + \sigma_B \\ & = a_1b_1 + \alpha_{12} + \beta_{21} + a_2b_2 + \alpha_{21} + \beta_{12} \\ & = a_1b_1 + \alpha_{12} + \beta_{12} + \alpha_{21} + \beta_{21} + a_2b_2 \\ & = a_1b_1 + a_1b_2 + \beta_{12}' + \beta_{12} + a_2b_1 + \beta_{21}' + \beta_{21} + a_2b_2 \\ & = a_1b_1 + a_1b_2 + a_2b_1 + a_2b_2 \\ & = (a_1 + a_2)(b_1 + b_2) \end{split} \end{equation*}
Calculate $r$
Each party has a share of $k$ from which they can calculate $r$. They each generate a random integer $\gamma$ which they multiply by the generator point, $\Gamma = \gamma{}G$, and then share it with each other see Figure 1.3.
Figure 1.3 Share $\Gamma$ value
Each party then calculates $k^{-1}G$. First they calculate the value $k{}\gamma$ using MtA \begin{equation*} \begin{split} k\gamma & = (k_A + k_B).(\gamma_A + \gamma_B) \\ & = k_A\gamma_A + k_A\gamma_B + k_B\gamma_A + k_B\gamma_B \end{split} \end{equation*} The values $k_A\gamma_B$ and $k_B\gamma_A$ need to be additively shared. Alice is returned a value $\delta_A$ and Bob is returned a value $\delta_B$ \begin{equation*} \begin{split} \delta_A & = k_A\gamma_A + \alpha_{12} + \beta_{21} \\ \delta_B & = k_B\gamma_B + \alpha_{21} + \beta_{12} \end{split} \end{equation*} They then exchange their respective $\delta$ values and sum them. \begin{equation*} \begin{split} k\gamma & = \delta_A + \delta_B \\ & = k_A\gamma_A + \alpha_{12} + \beta_{21} + k_B\gamma_B + \alpha_{21} + \beta_{12} \\ & = k_A\gamma_A + \alpha_{12} + \beta_{12} + k_B\gamma_B + \alpha_{21} + \beta_{21} \\ & = k_A\gamma_A + k_A\gamma_B + \beta_{12}' + \beta_{12} + k_B\gamma_B + k_B\gamma_A + \beta_{21}' + \beta_{21} \\ & = k_A\gamma_A + k_A\gamma_B + k_B\gamma_A + k_B\gamma_B \\ & = (k_A + k_B).(\gamma_A + \gamma_B) \end{split} \end{equation*} Then they invert $k\gamma$ and multiple it by the sum of the $\Gamma$ points to calculate $r$ \begin{equation*} \begin{split} x,y & = (k\gamma)^{-1}(\Gamma_A + \Gamma_B) \\ & = \frac{1}{(k_A + k_B).(\gamma_A + \gamma_B)}(\gamma_A{}G + \gamma_B{}G) \\ & = \frac{1}{(k_A + k_B).(\gamma_A + \gamma_B)}(\gamma_A{} + \gamma_B{})G \\ & = \frac{1}{(k_A + k_B)}G \\ & = \frac{1}{k}G \\ r & = x\text{ }\mathrm{mod}\text{ }n \end{split} \end{equation*}
Calculate $s$
They calculate their share of $kw$ using MtA \begin{equation*} \begin{split} kw & = (k_A + k_B).(w_A + w_B) \\ & = k_Aw_A + k_Aw_B + k_Bw_A + k_Bw_B \end{split} \end{equation*} The values $k_Aw_B$ and $k_Bw_A$ need to be additively shared. Alice is returned a value $\sigma_A$ and Bob is returned a value $\sigma_B$ \begin{equation*} \begin{split} \sigma_A = k_Aw_A + \alpha_{12} + \beta_{21} \\ \sigma_B = k_Bw_B + \alpha_{21} + \beta_{12} \end{split} \end{equation*} Now the parties can calculate their share of $s$ for message $m$ such that $z=H(m)$; \begin{equation*} \begin{split} s_A = k_A(z + r\sigma_A) \\ s_B = k_B(z + r\sigma_B) \end{split} \end{equation*} Adding these values creates a valid $s$ value; \begin{equation*} \begin{split} s & = s_A + s_B \\ & = k_Az + r\sigma_A + k_Bz + r\sigma_B \\ & = k_Az + k_Bz + r(\sigma_A + \sigma_B) \\ & = k_Az + k_Bz + r(k_Aw_A + \alpha_{12} + \beta_{21} + k_Bw_B + \alpha_{21} + \beta_{12}) \\ & = k_Az + k_Bz + r(k_Aw_A + \alpha_{12} + \beta_{12} + \alpha_{21} + \beta_{21} + k_Bw_B) \\ & = k_Az + k_Bz + r(k_Aw_A + k_Aw_B + \beta_{12}' + \beta_{12} + k_Bw_A + \beta_{21}' + \beta_{21} + k_Bw_B) \\ & = k_Az + k_Bz + r(k_Aw_A + k_Aw_B + k_Bw_A + k_Bw_B) \\ & = k_Az + k_Bz + r(k_A + k_B)(w_A + w_B) \\ & = k(z + rw) \text{ }\mathrm{mod}\text{ }n \end{split} \end{equation*} For a complete description please see the papers:
- Rosario Gennaro and Steven Goldfeder. Fast multiparty threshold ecdsa with fast trustless setup. Cryptology ePrint Archive, Report 2019/114, 2019. https://eprint.iacr.org/2019/114.
- Rosario Gennaro and Steven Goldfeder. One round threshold ecdsa with identifiable abort. Cryptology ePrint Archive, Report 2020/540, 2020. https://eprint.iacr.org/2020/540.
To learn more about Qredo's MPC implementation, read the yellow paper.
