Studdy of the paper Threshold ECDSA from ECDSA Assumptions:The Multiparty Case in the contact of the MPC class at EURECOM.

  • Extend the 2-of-n signing protocol (Doerner et al) to t-of-n in \(log(t) + 6\) rounds
  • New MP functionnality
  • Replace key exchange by MP multiplication based alternative
  • New consistency check
  • optimisation of the protocol for this setup

Personal notation

  • \([n] = [1,n]\)
  • \(a := b\) : define \(a\) as \(b\)
  • \(a \leftarrow A \): sample \(a\) from set \(A\)
  • \( A:a \to X:x \): send \(a\) from set \(A\) to protocol, and get \(x\) from set \(X\) in output

ECDSA signature:

  • Curve: \((\mathbb{G}, G, q)\) (Where \(\mathbb{G}=\{G^i / i\in [q]\}\), and \(G^q=1\))
  • Secret key: \(sk\in\mathbb{Z_q}\)
  • Public Key: \(pk:=sk\cdot G\)
  • message: \(m\)
  • signature: \((sig, r_x)\in\mathbb{Z_q}^2\) (mod \(q\))

$$sig := \frac{H(m)+sk \cdot r_x}{k}$$

where \(k\in\mathbb{Z_q}\) uniformely choosen, and \(r_x\) is the \(x\) coordinate of the point \(R:=k\cdot G\).

  • verification

$$R’ := \frac{H(m)\cdot G + r_x\cdot pk}{sig} = (r’_x,r’_y)$$

Verify that \(r’_x = r_x\)

Setup protocol

Sharing protocol

Each of the \(n\) parties receive a point of a polynomial of degree \((t-1)\), which value at \(0\) is \(sk\) (Shamir’s secret sharing)

Signing protocol

Instance Key Multiplication

Each of the \(t\) computing parties \(\mathcal{P_i}\) sample \(k_i\), a multiplicative share of \(k\). A \(t\) party multiplication protocol gives an additive sharing of \(k\) and a multiplicatively padded additive sharing of \(\frac{1}{k}\)

TODO: additive or multiplication? multiplicatively padded?

Secret Key multiplication

GMW-style multiplication to obtain \(\frac{sk}{k}\)

Consistency check

The parties compute \(R = k\cdot G\) and check the consistency of the inputs. Same consistency protocol has with Doerner et al., but in broadcast + additionnal relashionship. Everyone must have used consistent inputs between the Instance Key Multiplication and the Secret Key Multiplication.

Signing

If all inputs are consistant, each parties \(\mathcal{P_i}\) holds \(v_i,w_i\) and \(R\) such that for some value \(k\)

$$\sum_{i\in P} v_i = \frac{1}{k}$$

$$\sum_{i\in P} w_i = \frac{sk}{k}$$

$$R = k\cdot G$$

The parties compute \(sig_i = v_i\cdot H(m) + w_i\cdot r_x\), broadcast there share, than \(sig\) is reconstructed:

$$sig = \sum_{i\in P} sig_i$$

Protocol 1: two party multiplication \(\pi^l_{2PMul}\)

  • Alice: \(\mathbb{Z_q}^l:a \to \mathbb{Z_q}^l:z_A\)
  • Bob: \(\mathbb{Z_q}^l:b \to \mathbb{Z_q}^l:z_B\)

$$\forall i \in [l], z_{A,i}+z_{B,i} = a_i\cdot b_i$$

Encoding

Bob:

  • Samples \(\beta \leftarrow \{0,1\}^{l\cdot \zeta}\)
  • Defines \(\tilde{b} := \{<g,\{\beta_j\}_{j\in [i\cdot\zeta+1, (i+1)\cdot \zeta]}>\}_{i\in [l]}\)

Alice:

  • Samples \(\tilde{a} \leftarrow \mathbb{Z_q}^l\)
  • Samples \(\hat{a} \leftarrow \mathbb{Z_q}^l\)
  • Defines \(\alpha = \{\tilde{a}_1 || \hat{a}_1\}_{j\in [\zeta]} || … || \{\tilde{a}_n || \hat{a}_n\}_{j\in [\zeta]} \in \mathbb{Z_q}^{\zeta\cdot l}\) QUESTION: wtf does \(j\)?

Multiplication

Using \(\mathcal{F}^{\zeta\cdot l}_{COTe}\):

  • Alice \(\alpha \to \mathbb{Z_q}^{\zeta\cdot l}: \omega_A \)
  • Bob: \(\beta \to \mathbb{Z_q}^{\zeta\cdot l}: \omega_B \)

$$\omega_A = \{\tilde{z}_{A,j} || \hat{z}_{A,j}\}_{j\in [\zeta\cdot l]}$$ $$\omega_B = \{\tilde{z}_{B,j} || \hat{z}_{B,j}\}_{j\in [\zeta\cdot l]}$$

Alice-preprocess phase:

Alice and Bob use the Oracle to both generate

$$\tilde{\chi} \leftarrow H(1||transcript) \in \{0,1\}^l$$ $$\hat{\chi} \leftarrow H(1||transcript) \in \{0,1\}^l$$

Alice sends \(r\) and \(u\) to Bob

$$r := \{\sum_{i\in [l]} \tilde{\chi}_i \cdot \tilde{z}_{A,i\cdot \zeta + j} + \hat{\chi}_i \cdot \hat{z}_{A,i\cdot \zeta + j} \}_{j\in [\zeta]} \in ??^\zeta$$

$$ u:= \{\tilde{\chi}_i\cdot\tilde{a}_i + \hat{\chi}_i\cdot\hat{a}_i\}_{i\in [l]} \in \mathbb{Z}_q^l$$

Bob abort if

$$\lor_{i\in [\zeta]} (r_j + \sum_{i\in [l]} (\tilde{\chi}_i \cdot \tilde{z}_{B,i\cdot \zeta + j} + \hat{\chi}_i \cdot \hat{z}_{B,i\cdot \zeta + j}) \neq \sum_{i\in [l]} \beta_{i\cdot\zeta+j}\cdot u_i)$$

Alice input + Bob input + Alice input rush

  • Alice sends \(\gamma_A := \{a_i-\tilde{a}_i\}_{i\in [l]}\) to Bob
  • Bob sends \(\gamma_B := \{b_i-\tilde{b}_i\}_{i\in [l]}\) to Alice

$$z_A := \{a_i\cdot \gamma_{B,i} + \sum_{j\in [\zeta]} g_j\cdot\tilde{z}_{A,i\cdot\zeta + j} \}_{i\in [l]}$$ $$z_B := \{b_i\cdot \gamma_{A,i} + \sum_{j\in [\zeta]} g_j\cdot\tilde{z}_{B,i\cdot\zeta + j} \}_{i\in [l]}$$

Alice input rush

This phase is here to simulate a simultaneous simulation: Bob and Alice can both be the first to send a message here, emulating the behavior of an adversary trying to break the simultaneity condition.

Questions

Funct 4

For \(\mathcal{F}_{2PMul}^l\), in the stage Bob-input, we have \(z_A := \{a_i\cdot b_i - z_{B,i}\}_{i\in [1,l]}\), with \((a,b)\in\mathbb{Z_q}^2\) and \(z_B\in\mathbb{Z_q}^l\). QUESTION: what are \(a_i\) and \(b_i\)?

And in Alice-rush, \(z_A\in\mathbb{Z_q}\)? not \(\mathbb{Z_q}^l\)?

OK, this is a mistake in the paper, everything is in \(\mathbb{Z_q}^l\).