Published Dec 16, 2020 9:45:38 AM

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.

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*}

**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*}

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_Az + r\sigma_A \\ s_B = k_Bz + 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.