GG20

Intro §

In a threshold signature scheme, a key is split into $n$ shares and a parameter $t$ is defined such that an adversary that compromises $t$ or fewer shares is unable to generate a signature and learns no information about the key. On the other hand, in a threshold optimal scheme, $t+1$ shares can be used to jointly issue a signature without ever reconstructing the key.

Overview §

A standard way to identify malicious players is to require each player to prove in zero-knowledge that he is performing the protocol correctly, though alternative approaches exist.

Our key observation however is that if the abort happens during the preprocessing stage then the full signature has not been revealed yet (and indeed the message being signed may not even be known at this point). Therefore it is safe for the players to reveal the random choices they made during the protocol so far (that includes “opening up” any encryption, etc.) so that their behavior can be verified, and bad players identified.

Moreover, an abort during the online stage can be easily attributed as the shares of the signature s that each player reveals can be easily checked to be correct against public information produced by the offline stage.

ECDSA Security §

We assume a stronger notion of unforgeability for ECDSA. In this notion we allow the attacker to see the randomizer R before queriying the message $m$ during a chosen-message attack.

This is secure in the presence of a state compromise attack - where the adversary is allowed to see the internal state of the signer (but not its secret keys). This models the real-life situation in which the signer pre-computes all the randomizers $R$’s in advance and stores them in regular memory (while keeping the secret key $x$ and the secret nonces $k$ in a protected memory). We assume that the adversary manages to read the regular memory contents (i.e. all the $R$’s) and still will not be able to forge.

Additively Homomorphic Encryption §

Uses Paillier’s additively homomorphic encryption scheme for additions - specifically it is additively homomorphic modulo a large integer $N$:

• Given ciphertexts $c_1=E_{pk}(a)$ and $c_2=E_{pk}(b)$ there is an efficiently computable function ${+}_E$ such that $c_1{+}_E{c}_2=E_{pk}(a+b\mathrm{mod}N)$ .
• The existence of a ciphertext addition also implies a scalar multiplication operation, ${\times }_E$ . Given an integer $a\in \mathbb{N}$ and a ciphertext $c=E_{pk}(m)$ then we have $a{\times }_{E}c=E_{pk}(am\mathrm{mod}N)$.

Recall the details of such scheme:

• Key-Gen: $N=PQ$ where $P$ and $Q$ are randomly generated large primes of equal length.
• Decryption
• Homomorphic properties: Given two ciphertexts $c_1,c_2\in {\mathbb{Z}}_{N^2}$ define $c_1{+}_E{c}_2=c_1{c}_2\mathrm{mod}{N}^2$. If $c_i=E(m_i)$ then $c_1{+}_E{c}_2=E(m_1+m_2\mathrm{mod}N)$ . Similarly, given a ciphertext $c=E(m)\in {\mathbb{Z}}_{N^2}$ and a number $a\in {\mathbb{Z}}_{N^2}$ we have that $a{\times }_{E}c=c^a\mathrm{mod}{N}^2=E(am\mathrm{mod}N)$ .

Non-Malleable Equivocable Commitments §

A trapdoor commitment scheme allows a sender to commit to a message with information-theoretic privacy. i.e., given the transcript of the commitment phase the receiver, even with infinite computing power, cannot guess the committed message better than at random.

This trapdoor should be hard to compute efficiently.

A non-interactive trapdoor commitment scheme consists of the following four algorithms:

• $KG$ is the key generation algorithm, on input the security parameter it outputs a pair {$pk$, $tk$} where $pk$ is the public key associated with the commitment scheme, and $tk$ is called the trapdoor.
• $Com$ is the commitment algorithm. On input $pk$ and a message $M$ it outputs $[C(M),D(M)]=Com(pk,M,R)$ where $r$ are the coin tosses. $C(M)$ is the commitment string, while $D(M)$ is the decommitment string, which is kept secret until opening time.
• $Ver$ is the verification algorithm. On input $C$, $D$ and $pk$ it either outputs a message $M$ $or$\perp$
• $Equiv$ is the algorithm that opens a commitment in any possible way given the trapdoor information. It takes as input $pk$, strings $M$, $R$ with $[C(M),D(M)]=Com(pk,M,R)$, a message $M\ne M^{\prime }$ and a string $T$. If $T=tk$ then $Equiv$ outputs $D^{\prime }$ such that $Ver(pk,C(M),D^{\prime })=M^{\prime }$ .

Trapdoor commitments must satisfy:

• Correctness
• Information theoretic security
• Secure binding

Some commitment schemes are not concurrently secure and have a security definition that only holds for $t=1$, ie. the adversary only sees 1 commitment. A stronger commitment scheme used here is to use any secure hash function $H$ and define the commitment to $x$ as $h=H(x,r)$ for a uniformly chosen $r$ of length $\lambda$ and assume that $H$ behaves as a random oracle.

Multiplicative-to-Additive Share Conversion Protocol §

This protocol converts multiplicative shares of a secret into additive shares.

Assume that we have two parties Alice and Bob holding two secrets $a$, $b\in {\mathbb{Z}}_q$ respectively which we can think of as multiplicative shares of a secret $x=ab\mathrm{mod}q$. Alice and Bob would like to compute secret additive shares $\alpha$, $\beta$ of $x$, that is random values such that $\alpha +\beta =x=ab\mathrm{mod}q$ with Alice holding $\alpha$ (and $a$) and Bob holding $\beta$ (and $b$).

In the basic MtA protocol, the player’s inputs are not verified, and the players can cause the protocol to produce an incorrect output by inputting the wrong values $\hat{a}$ , $\hat{b}$ . In the case when $B=g^b$ is public, the protocol can be enhanced to include an extra check that ensures that $P_2$ inputs the correct value $b=lo{g}_g(B)$ - this protocol is called MtAwc (MtA “with check”).

In this protocol, zero-knowledge range proofs and proofs of knowledge are used to verify the commitments. If the proofs fail to verify, the verifying party aborts. The verifier generates the parameters $\tilde{N}$, $h1$ and $h2$ and prove the discrete log between $h1$ and $h2$ exist.

• The proofs are generated here https://github.com/ZenGo-X/multi-party-ecdsa/blob/c94065fbf37132dccc7955cf2627866e87c162bf/src/protocols/multi_party_ecdsa/gg_2020/party_i.rs#L239-L225

Q: Why is this share conversion necessary?

Feldman Verifiable Secret Sharing §

In Shamir’s secret sharing scheme, to share a secret $\sigma \in {\mathbb{Z}}_q$ the dealer generates a random degree $t$ polynomial $p(\cdot )$ over ${\mathbb{Z}}_q$ such that $p(0)=\sigma$ . The secret shares are evaluations of the polynomial:

$p(x)=\sigma +a_{1}x+a_2{x}^2+...+a_t{x}^t\mathrm{mod}q$

Each Player $P_i$ receives a share ${\sigma }_i=p(i)\mathrm{mod}q$ .

In a verifiable secret sharing scheme, auxiliary information is published that allows players to check that their shares are consistent and define a unique secret. Feldman’s VSS is an extension of Shamir secret sharing in which the dealer also publishes $v_i=g^{a_i}$ in $G$ for all $i\in [1,t]$ and $v_0=g^{\sigma }$ in $G$.

Using this auxiliary information, each Player $P_i$ can check its share ${\sigma }_i$ for consistency by verifying:

$g^{{\sigma }_i}={\prod }_{j=0}^t{v}_j^{i^j}$ in $G$

If the check does not hold for any player, it raises a complaint and the protocol terminates.

Feldman’s scheme does leak $g^{\sigma }$ but nothing else.

Key Generation Protocol §

Summary:

• In Phase 1, each player generates a random scalar $u_i$ and its corresponding public component, an EC point $y_i$, and makes a public, verifiable commitment to that $y_i$ parameter.
  • $y_i$ is necessary for the public commitment, and $u_i$ is meant to be kept private.
• In Phase 2, each player performs VSS of $u_i$, and use the received shares from other players to create their own secret key share $x_i$. Each key share has a corresponding public key $X_i=g^{x_i}$
• In Phase 3, each player proves that they own $x_i$.

Phase 1:

• Each Player $P_i$ chooses a random scalar $u_i{\in }_R{\mathbb{Z}}_q$ and runs the commitment algorithm.
  • $u_i$ is chosen here https://github.com/ZenGo-X/multi-party-ecdsa/blob/c94065fbf37132dccc7955cf2627866e87c162bf/src/protocols/multi_party_ecdsa/gg_2020/party_i.rs#L160
  • The public key (each Player’s individual keypair is generated after the VSS in Phase 2) EC Point $y_i=g^{u_i}$ is generated here using $u_i$ https://github.com/ZenGo-X/multi-party-ecdsa/blob/c94065fbf37132dccc7955cf2627866e87c162bf/src/protocols/multi_party_ecdsa/gg_2020/party_i.rs#L161
  • The Paillier encryption key $E_i$ (and decryption key) are generated here https://github.com/ZenGo-X/multi-party-ecdsa/blob/c94065fbf37132dccc7955cf2627866e87c162bf/src/protocols/multi_party_ecdsa/gg_2020/party_i.rs#L162
  • The Hash commitment to $y_i$ is made https://github.com/ZenGo-X/multi-party-ecdsa/blob/c94065fbf37132dccc7955cf2627866e87c162bf/src/protocols/multi_party_ecdsa/gg_2020/party_i.rs#L241-L244.
    • The user defined randomness $r$ is chosen here https://github.com/ZenGo-X/multi-party-ecdsa/blob/c94065fbf37132dccc7955cf2627866e87c162bf/src/protocols/multi_party_ecdsa/gg_2020/party_i.rs#L222
• Each Player $P_i$ broadcasts $KG{C}_i$ and $E_i$ .

Phase 2:

• Each Player $P_i$ broadcasts $KG{D}_i$.
• Let $y_i$ be the value decommitted by $P_i$. The Player $P_i$ performs a $(t,n)$ Feldman-VSS of the value $u_i$ with $y_i$ as the “free term in the exponent”.
  • Shares for VSS of $u_i$ created here https://github.com/ZenGo-X/multi-party-ecdsa/blob/c94065fbf37132dccc7955cf2627866e87c162bf/src/protocols/multi_party_ecdsa/gg_2020/party_i.rs#L313-L314
• The (distributed) public key is set to $y={\prod }_i{y}_i$ . Each player adds the private shares received during the $n$ Feldman VSS protocols. The resulting values $x_i$ are a $(t,n)$ Shamir’s secret sharing of the (distributed) secret key $x={\sum }_i{u}_i$ . Note that the values $X_i=g^{x_i}$ are public.
  • Private shares added to get $x_i$ here https://github.com/ZenGo-X/multi-party-ecdsa/blob/c94065fbf37132dccc7955cf2627866e87c162bf/src/protocols/multi_party_ecdsa/gg_2020/party_i.rs#L359-L361

Phase 3:

• Let $N_i=p_i{q}_i$ be the RSA modulus associated with $E_i$. Each player $P_i$ proves in ZK that he knows $x_i$ using Schnorr’s protocol, that $N_i$ is square-free, and that $h1$, $h2$ generate the same group modulo $N_i$.
  • Discrete log proof of $x_i$ here https://github.com/ZenGo-X/multi-party-ecdsa/blob/c94065fbf37132dccc7955cf2627866e87c162bf/src/protocols/multi_party_ecdsa/gg_2020/party_i.rs#L362
  • Doesn’t seem like ZenGo implemented the proofs for $N_i$, $h1$ and $h2$?

Q: Does each $u_i$ need to be sufficiently large? Or just the prime $q$ needs to be large?

Signing Protocol §

In summary:

• Start with additive sharings of $x$, $k$ and use technique to create additive sharings of $k^{-1}$ and $kx$, and by linear homomorphism, additive shares of $s$. Then a “distributed signature verification” check is performed on shares of $s$ to make sure they reconstruct a correct signature.
• Our first major observation is that we identify a new distributed verification check can be performed on the shares of $k^{-1}$ and $kx$ before the message is known, and therefore can be done in a pre-processing phase. If those sharings are consistent and correct, then it is safe to reveal shares of $s$ once the message $m$ is known. This will take just a single scalar multiplication per player and one communication round (i.e. each player sends just a single message) and no online interactivity is required.
• In Phase 0, each player transforms their $(t,n)$ share $x_i$ into $(t,t+1)$ share $w_i$.
• In Phase 1, each player generates their own $k_i,{\gamma }_i$ as multiplicative shares of $k\gamma$, and broadcasts their commitment to ${\gamma }_i$ (via its corresponding public point generated by $g$)
• In Phase 2, MtA protocol is used to produce additive shares $\alpha ,\beta ,\mu ,v$ . These are then used to produce ${\delta }_i$ and ${\sigma }_i$.
• In Phase 3, $\delta$ is computed for use in Phase 4.
• In Phase 4, decommitments are presented and $R,r$ are computed.
• In Phase 5, 6 consistency checks are made based on ZK proofs.
• In Phase 7, the signature $(r,s[,v])$ is produced using $m$.

Preliminaries (Phase 0):

• Let $S\subseteq [\mathrm{1..}n]$ be the set of players participating in the signature protocol.
• Assume $|S|=t+1$. For the signing protocol we can share any ephemeral secrets using a $(t,t+1)$ secret sharing scheme, and do not need to use the general $(t,n)$ structure.
• Using the appropriate Langrangian coefficients ${\lambda }_{i,S}$ each player in S can locally map its own $(t,n)$ share $x_i$ of $x$ into a $(t,t+1)$ share of $x$, $w_i=({\lambda }_{i,S})(x_i)$, i.e. $x={\sum }_{i\in S}{w}_i$ . Since $X_i=g^{x_i}$ and ${\lambda }_{i,S}$ are public values, all the players can compute $W_i=g^{w_i}=X_i^{{\lambda }_{i,S}}$ .
  • ${\lambda }_{i,S}$ is computed here https://github.com/ZenGo-X/multi-party-ecdsa/blob/c94065fbf37132dccc7955cf2627866e87c162bf/src/protocols/multi_party_ecdsa/gg_2020/party_i.rs#L553
    • Computes the contribution of this $i$-th index towards the Lagrange basis polynomial evaluated at the zero point https://github.com/ZenGo-X/curv/blob/1a6541192f59aa447dc36cb13f88a5d09fd59dda/src/cryptographic_primitives/secret_sharing/feldman_vss.rs#L276
  • $w_i$ is computed here https://github.com/ZenGo-X/multi-party-ecdsa/blob/c94065fbf37132dccc7955cf2627866e87c162bf/src/protocols/multi_party_ecdsa/gg_2020/party_i.rs#L558

Phase 1:

• Each Player $P_i$ selects $k_i,{\gamma }_i{\in }_{\mathbb{R}}{\mathbb{Z}}_q$ .
  • Define $k={\sum }_{i\in S}{k}_i$ and $\gamma ={\sum }_{i\in S}{\gamma }_i$
  • Note that $k\gamma ={\sum }_{i,j\in S}{k}_i{\gamma }_i\mathrm{mod}q$ and $kx={\sum }_{i,j\in S}{k}_i{w}_i\mathrm{mod}q$
  • $k_i$ and ${\gamma }_i$ chosen here https://github.com/ZenGo-X/multi-party-ecdsa/blob/c94065fbf37132dccc7955cf2627866e87c162bf/src/protocols/multi_party_ecdsa/gg_2020/party_i.rs#L561-L563
• Each Player computes $[C_i,D_i]=Com(g^{{\gamma }_i})$ and broadcasts $C_i$.
  • The hash commitment to $g^{{\gamma }_i}$ is made here https://github.com/ZenGo-X/multi-party-ecdsa/blob/c94065fbf37132dccc7955cf2627866e87c162bf/src/protocols/multi_party_ecdsa/gg_2020/party_i.rs#L577

Phase 2:

• Every pair of players $P_i,P_j$ engages in two multiplicative-to-additive share conversion subprotocols. Note that the first message for these protocols is the same and is only sent once.
• $P_i,P_j$ run MtA with shares $k_i,{\gamma }_j$ respectively. Let ${\alpha }_{ij}$ and ${\beta }_{ij}$ be the share received by player $P_i$ and $P_j$ respectively at the end of this protocol, ie. $k_i{\gamma }_j={\alpha }_{ij}+{\beta }_{ij}$
  • Player $P_i$ sets ${\delta }_i=k_i{\gamma }_j+{\sum }_{j\ne i}{\alpha }_{ij}+{\sum }_{j\ne i}{\beta }_{ji}$
  • Note that the ${\delta }_i$ are a $(t,t+1)$ additive sharing of $k\gamma ={\sum }_{i\in S}{\delta }_i$
  • Step 1 of MtA against $k_i$ is done by $P_i$ here https://github.com/ZenGo-X/multi-party-ecdsa/blob/c94065fbf37132dccc7955cf2627866e87c162bf/src/protocols/multi_party_ecdsa/gg_2020/state_machine/sign/rounds.rs#L85
  • Step 2 of MtA against ${\gamma }_j$ is done by $P_j$ here https://github.com/ZenGo-X/multi-party-ecdsa/blob/c94065fbf37132dccc7955cf2627866e87c162bf/src/protocols/multi_party_ecdsa/gg_2020/state_machine/sign/rounds.rs#L150
  • ${\delta }_i$ is set here https://github.com/ZenGo-X/multi-party-ecdsa/blob/c94065fbf37132dccc7955cf2627866e87c162bf/src/protocols/multi_party_ecdsa/gg_2020/state_machine/sign/rounds.rs#L265
• $P_i,P_j$ run MtAwc with shares $k_i$, $w_j$ respectively. Let ${\mu }_{ij}$ and $v_{ij}$ be the share received by player $P_i$ and $P_j$ respectively at the end of this protocol, ie. $k_{i}wj=\mu ij+v_{ij}$
  • Player $P_i$ sets ${\sigma }_i=k_i{w}_j+{\sum }_{j\ne i}{\mu }_{ij}+{\sum }_{j\ne i}{v}_{ji}$
  • Note that the ${\sigma }_i$ are a $(t,t+1)$ additive sharing of $kx={\sum }_{i\in S}{\sigma }_i$
  • Step 2 of MtA against $w_j$ is done by $P_j$ here https://github.com/ZenGo-X/multi-party-ecdsa/blob/c94065fbf37132dccc7955cf2627866e87c162bf/src/protocols/multi_party_ecdsa/gg_2020/state_machine/sign/rounds.rs#L157
  • ${\sigma }_i$ is set here https://github.com/ZenGo-X/multi-party-ecdsa/blob/c94065fbf37132dccc7955cf2627866e87c162bf/src/protocols/multi_party_ecdsa/gg_2020/state_machine/sign/rounds.rs#L267

Phase 3:

• Every Player $P_i$ broadcasts:
  • ${\delta }_i$ and the players reconstruct $\delta ={\sum }_{i\in S}{\delta }_i=k\gamma$ . The players compute ${\delta }^{-1}\mathrm{mod}q$
  • $T_i=g^{{\sigma }_i}{h}^{l_i}$ with $l_i{\in }_R{\mathbb{Z}}_q$ and proves in ZK that he knows ${\sigma }_i,l_i$
    • $T_i$ computed here https://github.com/ZenGo-X/multi-party-ecdsa/blob/c94065fbf37132dccc7955cf2627866e87c162bf/src/protocols/multi_party_ecdsa/gg_2020/state_machine/sign/rounds.rs#L268
    • $h$ is just an alternative generator to $g$.
    • Uses (Chaum-)Pedersen proof https://github.com/ZenGo-X/multi-party-ecdsa/blob/c94065fbf37132dccc7955cf2627866e87c162bf/src/protocols/multi_party_ecdsa/gg_2020/party_i.rs#L631

Phase 4:

• Each Player $P_i$ broadcasts their decommitment $D_i$
  • Done here https://github.com/ZenGo-X/multi-party-ecdsa/blob/c94065fbf37132dccc7955cf2627866e87c162bf/src/protocols/multi_party_ecdsa/gg_2020/state_machine/sign/rounds.rs#L352
• Let ${\Gamma }_i$ be the values decommitted by $P_i$ . The players compute $\Gamma ={\prod }_{i\in S}{\Gamma }_i$ and $R={\Gamma }^{{\delta }^{-1}}=g^{({\sum }_{i\in S}{\gamma }_i)k^{-1}{\gamma }^{-1}}=g^{\gamma k^{-1}{\gamma }^{-1}}=g^{k^{-1}}$
  • $R$ is computed here https://github.com/ZenGo-X/multi-party-ecdsa/blob/c94065fbf37132dccc7955cf2627866e87c162bf/src/protocols/multi_party_ecdsa/gg_2020/state_machine/sign/rounds.rs#L412
• The players also compute $r=H^{\prime }(R)=R_x\mathrm{mod}q$

Phase 5:

• Each Player $P_i$ broadcasts ${\bar{R}}_i=R^{k_i}$ and a ZK proof of consistency between $R_i$ and $E_i(k_i)$ which each player sent as the first message of the MtA protocol in Phase 2. If $g\ne {\prod }_{i\in S}{\bar{R}}_i$ the protocol aborts.
  • ZK proof generated here https://github.com/ZenGo-X/multi-party-ecdsa/blob/c94065fbf37132dccc7955cf2627866e87c162bf/src/protocols/multi_party_ecdsa/gg_2020/state_machine/sign/rounds.rs#L433

Phase 6:

• Each Player $P_i$ broadcasts $S_i=R^{{\sigma }_i}$ and a ZK proof of consistency between $S_i$ and $T_i$ which each player sent in Phase 3. If $y\ne {\prod }_{i\in S}{S}_i$ the protocol aborts.
  • ZK proof generated here https://github.com/ZenGo-X/multi-party-ecdsa/blob/c94065fbf37132dccc7955cf2627866e87c162bf/src/protocols/multi_party_ecdsa/gg_2020/state_machine/sign/rounds.rs#L529
  • Uses the Homomorphic El Gamal Proof - proof of knowledge that a pair of group elements {D, E} form a valid homomorphic ElGamal encryption (”in the exponent”) using public key $Y$ .

Phase 7:

• Each Player $P_i$ broadcasts $s_i=m{k}_i+r{\sigma }_i$ and set $s=\sum s_i$ . If the signature $(r,s)$ is correct for $m$, the players accept, otherwise they abort.

Identifying Aborts §

Overview §

A standard way to identify malicious players is to require each player to prove in zero-knowledge that he is performing the protocol correctly, though alternative approaches exist.

Our key observation however is that if the abort happens during the preprocessing stage then the full signature has not been revealed yet (and indeed the message being signed may not even be known at this point). Therefore it is safe for the players to reveal the random choices they made during the protocol so far (that includes “opening up” any encryption, etc.) so that their behavior can be verified, and bad players identified.

Moreover, an abort during the online stage can be easily attributed as the shares of the signature $s$ that each player reveals can be easily checked to be correct against public information produced by the offline stage.

Key Generation §

In the key generation protocol, there are two possible places that an abort can occur:

• Phase 2: If a player complains that the Feldman share it received is inconsistent and therefore does not verify correctly, the protocol will abort.
  • Here there is ambiguity who the bad player is - whether the complainer is framing the complainee, or the complainee actually dealt a bad share.
  • A simple identification method is simply to publish the dealt share (and the message signature) into the open and let everyone verify. This is fine because the key share hasn’t been used to sign yet.
• Phase 3: When each player is proving knowledge of $x_i$ and proving the correctness of their Paillier key, if one of these proofs fails to verify the protocol will abort.

Signing Protocol §

In the signing protocol, there are places that an abort can occur:

• Phase 2: If the range proofs of the MtA / MtAwc or ZK proofs for MtAwc fail.
• Phase 3: If the ZK proof about ${\sigma }_i,l_i$ fails
• Phase 4: If the decommitment $D_i$ fails to verify
• Phase 5: If the ZK proof about ${\bar{R}}_i$ fails to verify
• Phase 5: If $g\ne \prod {\bar{R}}_i$
• Phase 6: If the ZK proof about $S_i$ fails to verify
• Phase 6: If $y\ne \prod S_i$
• Phase 7: If the signature $(r,s)$ is not valid for the message $m$.

Resources §

https://eprint.iacr.org/2020/540.pdf