February 2, 2023 | 24 min Read

Demystifiying SMPC (Secure multi-party computation) and its threat model

Prologue

SMPC is an interesting topic, whose the applications include systematic security and cryptographic engineering, and this article will discuss its principles, threat models and use-case.

History and substantiation of SMPC

Secure Multiparty Computation (SMPC) is a branch of cryptography dated to 1979 by A. Shamir, R. Rivet and L. Adleman in the Mental Poker Secret Split, and then Andrew Chi-Chi Yao, officially proposed in 1982 through the “Millionaire Problem”.

In 1986, Yao proposed Garbled Circuit Protocol, which is still the basis for the most effective MPC implementations today.

In 1987, Goldrakh, Mikali and Wigderson extended two-party protocol to multi-party.

In the 1990s, MPC studies led to breakthroughs in universal composability and mobile security.

In 2008, the first large-scale practical application of SMPC was demonstrated at an auction in Denmark.

In the late 2010s, MPCs were first used by digital custody and digital wallets to protect digital assets.

In 2019, the MPC-CMP debuted with the first one-round operation, threshold DSA signature algorithm with automated key refreshing.

Threats and security requirements

Generally speaking, SMPC allows several participants to perform a computational process with confidential data that are at their own disposal as input data, without disclosing confidential data or intermediate results that can be used to compute confidential data to other participants.

The SMPC protocol should guarantee two main properties:

Privacy: No party has access to information, except for their own input and output data and what can be computed on the basis of their own input and output data.
Correctness: if any corrupted parties (for example, bribed by the adversary) act dishonestly, for example, share information in private or perform actions that deviate from the norms of the protocol, the protocol should not allow the dishonest parties to be able to make honest parties get the wrong result or disclose their secrets.

Ideal/realistic modeling paradigm: the list above is not a definition of security; It simply lists certain requirements that a secure protocol must comply with. On the contrary, the definition of security should include all important security requirements and cover all possible adversarial attacks. In addition, it should be simple and rather concise for practical use.

The current security standards are determined as follows. Consider the “ideal world”, where there is an external trusted party to help participants with their computations. In such a world, participants simply send their input data to the trusted parties on a fully protected channel, which then computes the selected functions and sends the relevant exits independently and secretly to each participant. Since the only action performed by participants is to send their input to the trusted side, the only freedom remaining for the adversary is to choose the input of the corrupted party (for example, a corrupted party wants to enter a, but the adversary asks them to enter a', and for other participants, the corrupted party input a', therefore, the final result generated by a' should be considered “correct” for other participants). Thus, in the ideal world, all safety requirements listed above would be fulfilled.

However, in the “real world”, no party can be trusted by all. On the contrary, the participants work together to execute the protocol without any outside help, and the corrupted parties can perform more dishonest operations. The protocol is called secure if it can imitate the results obtained in the ideal world described above, i.e. if the real protocol performed by participants guarantees that no adversary can cause more damage than if the attack was performed in an ideal world. This condition can be expressed as follows: so that any adversary can launch a successful attack in the real world, the adversary in the ideal world should always be able to successfully launch the same attack. However, in the ideal world, the attack could not be successfully fulfilled; Therefore, all real attacks on the implementation of the protocol must fail.

The above informal definition of security does not take into account the security model. In SMPC studies, the security model determines the capabilities of the adversary. The security of the protocol makes sense only if it is discussed within the framework of a certain security model. The protocol is considered safe only if it is resistant to any competitive attack in the framework of the corresponding security model. Depending on the behavior of the adversary, the security model can be divided into the following different types:

Semi-honest model: Corrupted parties can only execute the protocol honestly . However, the adversary has access to exhaustive information about the internal state of each corrupted party (including copies of all the information received) and will try to use these information to obtain other information which should be kept secret. Prevention of such attempts should be one of the most basic requirements of a secure protocol.
Malicious attack model: in addition to informing about all internal states, corrupted parties can also perform dishonest actions that are deviated from the specifications of the protocol under the instructions of the adversary. A secure protocol, immune to malicious attackers can guarantee that any malicious attack will end with an error. However, achieving this level of security requires a high price in terms of the effectiveness of the protocol, for example, dishonest interference in intermediate processes should be found in advance, leading to the abort of computations with a warning, or requiring a retry of an erroneous step, instead of emitting a specious result.
Hidden attack model: the Semi-honest model, described above, is too weak, but malicious attack model makes the protocol too ineffective in accordance with safety requirements. To overcome these difficulties, the hidden attack model was proposed. A secretive adversary can show malicious behavior, but they has a certain probability of being caught by honest participants. This models a number of financial or political conditions in which it cannot be assumed that all actions are honest, but involved companies and institutions cannot afford reputation damage associated with fraud. In this model, the adversary should weigh the risks of being caught against the advantages of deception. If a deception remains unnoticed, the result may be specious.

Committer

The most intuitively understandable form of the committer is: Alice generates a random number r and uses it as a key to encrypt a secret p, e = Enc(p, r), Alice first sends (commits) e to Bob, and then at some point Alice sends r to Bob, so Bob can decrypt (open) e to get p = Dec(e, r).

Oblivious transfer

Alice holds two secrets m(0) and m(1) to send to Bob, Bob can choose only one of two. Alice will not know what secret Bob chooses, and Bob does not know the secret that he does not choose.

Shimon Even, Oded Goldreich and Abraham Lempel used the nature of the RSA to propose an oblivious transfer scheme (see https://en.wikipedia.org/wiki/Oblivious_transfer#1%E2%80%932_oblivious_transfer) for preventing dishonest, the idea of which can be summarized as follows:

Alice randomly generates two values x(0) and x(1) and send to Bob, Bob randomly generates k locally, uses the nature of the public key encryption algorithm to encrypt k, mixed with the selected x(b) and sends it to Alice, which is equivalent to how Alice asks Bob to use the selected x(b) to “commit” k to her, and the role of the public key encryption algorithm is to prevent the leak of k from the channel. Since Alice cannot predict the value of k, she could ony use x(0) and x(1), which she knows to get the possible values k(0), k(1) by decryption, and use k(0) and k(1) as the keys to encrypt m(0) and m(1) and send to Bob, and Bob decrypt the corresponding ciphertext with k he knows. Bob has no chance to be dishonest when “committing” k, otherwise, neither k(0) nor k(1) will be equal to k, then Bob will not get anything.

Homomorphic encryption

The nature of some encryption algorithms lies in the fact that the effect of performing some operation with ciphertext is equivalent to perform plaintext operations, and then encrypting the result. Most common encryption algorithms usually have only partial homomorphism, that is, only a specific operation (for example, addition) for plaintexts can be achieved using the operations of ciphertext, and the operations of the ciphertext may not correspond to the same plaintext operation. Partial homomorphic encryption algorithms, which can keep certain operations with plaintext, are often used to implement the appropriate primitives of MPC operations, such as using an encryption algorithms that keeps multiplication to achieve MPC multiplication.

Zero-knowledge proof

A zero-knowledge proof or zero-knowledge protocol is a method by which one party (the prover) can prove to another party (the verifier) that a given statement is true while the prover avoids conveying any additional information apart from the fact that the statement is indeed true.

For example, Alice has Bob’s public key pkb, and Bob want to prove that he has the corresponding secret key skb.

Alice randomly generates r, and sends c = E(pkb, r) to Bob,
Bob decrypts c and sends the result of D(skb, c) to Alice, which should equal r.

Thus, Bob proves that he does hold skb without leaking any additional information.

However, c might be a ciphertext encrypted with pkb collected by Alice, and she might trick Bob to decrypt it for her, pretending to ask Bob for a zero-knowledge proof. To prevent this, Bob could in return request Alice to prove with zero-knowledge that she knows r in the first place. For example, he could randomly generate a salt s, send to Alice, and ask her to send h = Hash(r||s) along with c, and verify whether h equals Hash(D(skb, c)||s). (|| for concatenation of data string, using this salt to prevent Alice picking a precomputed h) If so, Bob sends D(skb, c) to Alice for her to verify, otherwise, Bob would know that Alice does not know r so that she might be dishonest, and he could just abort the conversation to avoid greater loss. With these improvements above, the protocol becomes this below:

Bob randomly generate s, and sends to Alice,
Alice randomly generates r, sends c = E(pkb, r), h = Hash(r||s) to Bob,
Bob computes d = D(skb, c) and verifies h == Hash(d||s). if so, he sends d to Alice, otherwise, he aborts the conversation to avoid greater loss.
Alice verifies that r == d.

Zero-knowledge proof schemes are usually used to confirm the correctness of intermediate results of multi-step MPC protocol. Although MPC may work without zero-knowledge proof, a multi-step MPC protocol without zero-knowledge proof is vulnerable against not only dishonest participants, but also unexpected errors, thus not an “SMPC” protocol.

Split a secret value x on GF(q) into n pieces. x could be restored when collecting t+1 pieces (called “shares”), but not t or less.

The method is shown below:

Select any t elements a(1) ~ a(t) in GF(q) and let x = a(0), build a polynomial x(e) ≡ a(0) + {i=1~t}Σ{a(i)e^i} ≡ {i=0~t}Σ{a(i)e^i} mod q, obviously x(0) is equal to x. Note: the process to compute and export x(e) = a(0) + {i=1~t}Σ{a(i)e^i} , is usually not supported by HSM, otherwise private key x could be computed via x(e) - ({i=1~t}Σ{a(i)e^i}) , contradicting with the property of HSM.
Randomly choose n (>t) pairs of [e(i), x(e(i))], (e(i) is the i-th sample value of the the independent variable e, all e(i) is not equal to 0 and differs), save a(1) ~ a(t) in secret or destroy, and appoint [e(i), x(e(i)] to the i-th participant.
After collecting 0~t, in total t+1 pairs, compute the constant term l(k,0) of the corresponding Lagrange basis polynomial, i.e. The value of the Lagrange basis polynomial when its independent variable is zero: l(k,0) ≡ {m=0~t, m!=k}Π{e(m)×inv(q, e(m)-e(k))} mod q, in which inv(q,x) is the multiplicative inverse of x with respect to the modulus q.
Now we can get x = x(0) ≡ {i=0~t}Σ{l(i,0)×x(e(i))} mod q.

Lagrange basis polynomial l(i,e(j)) = δ(i,j) = (i == j ? 1 : 0), i.e. l(i,e) gets 1 at e(i) and 0 in all the others e(j) where j != i, which is like a base vector,

Thus, the polynomial x(e) can be expressed as a linear combination of Lagrange basis polynomials, and their coefficients are equal to the value of x(e) at each e(i): x(e) ≡ {i=0~t}Σ{x(e(i))×l(i,e)} mod q, and then x(0) ≡ {i=0~t}Σ{x(e(i))×l(i,0)} mod q, in which l(i,0) is the value of the i-th Lagrange basis polynomial when its independent variable is zero, and equals its constant term, or Lagrange coefficient.

Thus, Shamir’s Secret Sharing could be described as: Taking the Lagrange coefficients l(i,0) as base vectors, an arbitrary secret x could be linearly expanded and its coordinates, i.e. the share, is the value of x(e) at each e(i), and l(i,0) is completely determined by each e(i). Because the rank of the linear space of all t-degree polynomials is (t+1), not less than (t+1) base vectors (Lagrange basis polynomials) are needed to express an arbitrary polynomial in such space.

It follows that Shamir’s secret sharing is linear to the coordinates, that is, the share. That is to say, if several secrets y(0) ~ y(m) is shared with the same set of e(i), obtaining coordinates y(j,e(i)), the arbitrary linear combination of y(0) ~ y(m), Y ≡ {j=0~m}Σ{b(j)y(j)} ≡ {j=0~m}Σ{b(j)×{i=0~t}Σ{y(j,e(i))×l(i,0)}} ≡ {i=0~t}Σ{{j=0~m}Σ{b(j)y(j,e(i))}×l(i,0)} ≡ {i=0~t}Σ{Y(e(i))×l(i,0)} mod q, in which Y(e(i)) ≡ {j=0~m}Σ{b(j)y(j,e(i))}. That is, assuming sharing with the same set of e(i), the sharing result of a linear combination of a set of secrets is equivalent to sharing those secrets individually and then linearly combining the sharing results in the same mode, which could be further written in matrix form: Y ≡ <b|y> ≡ <b|[y(j,e(i))]|l> ≡ <Y|l> mod q (row, column vectors, and are expressed with Dirac’s bra-ket notation),

Y = [ b(0) ~ b(m) ]×[y(0)  = [ b(0) ~ b(m) ]×[y(0,e(0))~y(0,e(t)) ×[l(0,0)  = [Y(e(0))~Y(e(t))]×[l(0,0)
	                  ~                         ~         ~            ~                            ~
                      y(m)]                     y(m,e(0))~y(m,e(t))]   l(t,0)]                      l(t,0)]

in which <b| is a row vector with m+1 dimensions, |y> ≡ [y(j,e(i))]|l>, is a column vector with m+1 dimensions, arranged with all secrets y(0) ~ y(m), [y(j,e(i))] is a matrix with m+1 rows and t+1 columns, each row of whose represents the sharing of the corresponding secret, while the column represents all the share received by the corresponding participant. |l> is a column vector with t+1 dimensions, arranged with Lagrange coefficients, <Y| ≡ <b|[y(j,e(i))] is a row vector with t+1 dimensions, arranged with the result of linear combination in the same mode of all received share by each participant.

This property has an important application in MPC-CMP: m = t is usually maded, and all b equals 1, y(0) ~ y(t) is generated or held by t+1 participants, with Y being their sum. They are then shared with the same set of e(i) to all the participant. Each participant then sums up all received shares, gets Y(e(i)). Multiplying with their corresponding Lagrange coefficient, Each participant gets their W(i) = Y(e(i))×l(i,0), the “Additive Secret Sharing” of Y = {j=0~t}Σ{y(j)}. The sum of all “Additive Secret Sharing” remains Y, but no participant can get y(i) owned by another participant.

Feldman-VSS

Based on Shamir’s Secret Sharing, making all t+1 samples of v(i) ≡ g^a(i) from 0~t, note that g^a(0) = g^x, while g is the generator of a cyclic group suitable of DH key exchange. Although individual participant does not know a(i), they can verify whether g^x(e(i)) ?≡ {j=0~t}Π{v(j)^(e(i)^j)}, because {j=0~t}Π{v(j)^(e(i)^j)} ≡ {j=0~t}Π{(g^a(j))^(e(i)^j)} ≡ {j=0~t}Π{g^(a(j)(e(i)^j)} ≡ g^({j=0~t}Σ{a(j)(e(i)^j}) ≡ g^x(e(i)), otherwise, the sharing process fails.

To make things simple, when describing Shamir’s and Feldman-VSS below, we would let e(i) = i, that is, for the i-th participant, [i, x(i)] is delivered as the share, in which x(i) is the value of polynomial x(e) when its independent variable takes the integer i, and because participants should know their sequence number, only x(i) should be transferred.

Paillier algorithm

Basically an extension of RSA, performed on Z(n^2), with the following partial homomorphism:

	Dp(sk, Ep(pk, a)×Ep(pk, b)) ≡ (a+b) mod n^2,
	Dp(sk, Ep(pk, b)^a) ≡ Dp(sk, Ep(pk, a)^b) ≡ (a×b) mod n^2.

MtA (for Multiplicative to Additive) secret conversion protocol

Alice and Bob hold a, b ∈ Z(q) respectively, they want to generate α and β, satisfying α + β ≡ a×b mod q, and Alice will hold a and α, Bob will hold b and β, without leaking to each other.

By using the Paillier algorithm above,

Alice sends c(A) = Ep(pkA, a) to Bob, and proves she knows the a < q^3 satisfying the computation process of c(A) with zero-knowledge. For example, Bob could randomly generate r, sends t(A) = c(A)×Ep(pkA, r) to Alice and requests Dp(skA, t(A)) - a, which should equal r.
Bob randomly selects β' in Z(q^5), sends c(B) = c(A)^b×Ep(pkA, β') = Ep(pkA, a×b)×Ep(pkA, β') = Ep(pkA, a×b+β') to Alice, let β = -β' mod q, and proves he knows the b < q^3 and β' < q^7 satisfying the computation process of c(B) with zero-knowledge. For example, Alice could send c'(A) = Ep(pkA, n^2-a) to Bob and requests c'(B) = c'(A)^b×Ep(pkA, n^2-β'), Dp(ska, c'(B)×c(B)) should equal 0. If B ≡ g^b is a public value, Bob should additionally prove that g^b == B with zero-knowledge.
Alice decrypts c(B) to obtain α' = a×b+β', let α = α' mod q. If B is public, Alice can randomly generate r', send to Bob, and request (g^β)^r', in order to verify that (g^β)^r'×g^(r'α) ≡ B^(r'a).

Now we assume that there are t+1 participants P(0)~P(t), each holding their own a(i), b(i). P(i) performs MtA secret conversion with P(j) to obtain α(i,j) held by P(i) and β(i,j) held by P(j), and applying “self conversion agreement”: α(i,i) = a(i)×b(i), β(i,i) = 0. Then each participant P(i) compute p(i) = {j=0~t}Σ{α(i,j)+β(j,i)}, so {i=0~t}Σ{p(i)} = {i=0~t}Σ{{j=0~t}Σ{α(i,j)+β(j,i)}} = {i,j=0~t}Σ{α(i,j)+β(j,i)} = {i,j=0~t}Σ{α(i,j)+β(i,j)} = {i,j=0~t}Σ{a(i)×b(j)} = ({i=0~t}Σ{a(i)})×({j=0~t}Σ{b(j)}, because all α(i,j) and β(i,j) are included in the range of sum. The whole process correspond to perform “Additive Secret Sharing” upon the product ab of a = {i=0~t}Σ{a(i)} and b = {j=0~t}Σ{b(j)} into p(i) = {j=0~t}Σ{α(i,j)+β(j,i)} held by each participant, without truly computing a, b and ab.

Non-Malleable Equivocable Commitments

If {pk, tk} = KG(seed), [C(M), D(M)] = Com(pk, M, R), then Ver(pk, C(M), D(M)) = M. There is D(M') = Equiv(pk, tk, M, R, M') satisfying Ver(pk, C(M), D(M')) = M'.

That is, D(M) could restore C(M) to M, but the result is not unique. Function Equiv() could be used to compute a D(M') that can decrypt C(M) into M'.

Generalized DSA-type signature algorithm

Defined on a cyclic group in which discrete logarithm is hard to resolve, the order of the group is prime number q, g is the generator. A scalar x is used as private key, X = g^x is the public key. If elliptic curves are concerned, capital letters are all used to represent points on an elliptic curve.

Choose a k “randomly”, let r = H'(g^k), e = H(m), s = inv(q,k)(e+xr) mod q, H(m) is a function to obtain a scalar from several leftmost bits of the hash of m. The pair (r,s) is the signature, and it is valid if and only if r == H'(g^(e×inv(q,s))×X^(rinv(q,s)))

In classic DSA, the cyclic group is the subgroup with order q (not unique) of a multiplicative group of integers modulo p that (p-1) is divisible by q. The generator g = h^((p-1)/q) mod p, in which h is randomly chosen among {2...(p-2)} and g != 1. H’(A) is A mod q.

In ECDSA, the cyclic group is the subgroup with order q of an additive group of points on an elliptic curve defined on a finite field. H'(A) is x(A) mod q, while x(A) returns the horizonal coordinate of point A on the elliptic curve.

k should have these three property below:

1. Randomness: It should be unable to compute from the data being signed (called "payload" below) and the resulted signature.
2. Confidentiality: It should not be leaked outside the signing process.
3. Uniqueness: It should be different for different payloads.

Otherwise, an attacker may compute the private key from payloads and signatures, for example, when k is leaked, we can obtain x = inv(q,r)(sk - H(m)).

If the random number comes from a flawed RNG, its randomness and uniqueness will become difficult to guarantee, for the attacker may find the pattern of the flawed RNG by collecting enough payload-signature pairs, and then compute the private key.

One of the methods to solve this problem is to derive the “random number” k deterministically from the hash value of private key and payload with irreversible algorithm (such as hash or message authentication code algorithm): The participation of private key in the derivation process guarantees property 1 and 3, if only the private key is not leaked. This method has been standardized as RFC 6979.

EdDSA algorithm

Though so named, EdDSA (RFC 8032) does not belong to generalized DSA-type algorithm. Instead, it is a mixture of signature algorithms of Schnorr and DSA in a cyclic subgroup with prime order q of an additive group of points on a twisted Edwards elliptic curve.

The private key t is a randomly-generated bit string. It is hashed with an algorithm generating results with 2b bits, and the result is split in two l(t) and h(t), with b bits each.
The private scalar x = (l(t)&i)|j, i, j are parameters dependent on the particular curve, used to set some bits of x to 0 or 1 uniformly. The generator G is a fixed point on the elliptic curve, and the cyclic subgroup generated by G has order q, while the largest cyclic group on the curve has order 2^c×q. The public key is X = xG. What corresponds to k is deterministically generated from the payload m and h(t) via hashing: k = H(h(t)||m) mod q, || for concatenation of data string.
R = kG is a point on the curve, e = H(R||X||m), s = (k + xe) mod q, the pair (R,s) forms the signature, verified via 2^c×s×G == 2^c×R + 2^c×e×X.

In the original Schnorr algorithm, e = H(R||m), s = (k - xe) mod q, and the signature consists of (s,e), verified via e == H((sG+eX)||m). EdDSA borrows (R,s) from generalized DSA-type algorithm, and make public key X participate the generation of e.

Contrary to ECDSA, EdDSA does not use an H'() function which only returns the horizonal coordinate of a point. Instead, EdDSA uses a coding scheme capable to represent a point on the twisted Edwards elliptic curve losslessly.

The private scalar x corresponds to the private key of generalized DSA-type and original Schnorr signature algorithm, while h(t) acts as a seed generated along with, but mathematically irrelated to the private scalar x, used to generate k, avoiding issues of randomly generate k in generalized DSA. The private key t yet acts as a seed to generate x and h(t). If t is saved, there would be no need to save x and h(t) at the same time.

Attacks against EdDSA usually aim at obtaining the private scalar x, instead of the private key t, because one possessing x could already generate valid signature by randomly choosing h(t) or k.

A false public key attack against EdDSA

In the step s = (k + x(e = H(R||X||m))) mod q, X = xG must be guaranteed, otherwise, a false public key attack could be performed to obtain the private scalar x:

Injecting an X' != xG the adversary knows, to produce s' = (k + x(e' = H(R||X'||m))) mod q, the adversary could obtain x = (s'-s)inv(q,(e'-e)) mod q.

MPC-CMP: multi-party DSA

In this protocol, the standing of k and inv(q,k) in generalized DSA we discussed above is swapped, that is, r = H'(g^inv(q,k)), s = k(e+xr) mod q, in order to guarantee that k and s could be computed distributively.

The exact steps are shown below: 0. Each participant holds their own u(i), publishes g^u(i) as their personal public key, and shares u(i) via Feldman-VSS to every other participant, let a(i,j) be the j-th polynomial coefficient generated by the i-th participant, v(i,j) = g^a(i,j) is published to verify the validity of Feldman-VSS. Each participant sums up all received shares x(i,j) to get x(i) = {j}Σ{x(i,j)}, multiplied with the corresponding Lagrange coefficient to get w(i) = x(i)×l(i,0), being the “Additive Secret Sharing” of x = {i}Σ{u(i)}. x acts as the collective private key, while X = {i}Π{g^u(i)} = g^({i}Σ{u(i)}) = g^x acts as the collective public key. In the mean time, the X(i) = {j=0~t}Π{v(i,j)^(i^j)} = g^x(i) obtained from the step of Feldman-VSS could be used to compute W(i) = X(i)^l(i,0) = g^w(i).

Each participant randomly generates k(i), γ(i), commits {C(i),D(i)} = Com(g^γ(i)), and broadcasts C(i), let k = {i}Σ{k(i)}, γ = {j}Σ{γ(j)}, converts k(i)×γ(j) = α(i,j)+β(i,j) with MtA (applying the “self conversion agreement” here), and let δ(i) = {j}Σ{α(i,j)+β(j,i)}.
Each participant converts k(i)×w(j) = µ(i,j)+ν(i,j) and checks w(i) with W(i), let σ(i) = {j}Σ{µ(i,j)+ν(j,i)}. Thus, {i}Σ{δ(i)} = kγ, {i}Σ{σ(i)} = k×{j}Σ{w(j)} = kx.
Each participant broadcasts their own δ(i), and computes δ = {i}Σ{δ(i)} = kγ, and inv(q,δ) mod q.
Each participant broadcasts their own D(i) to open Γ(i) = g^γ(i), and computes R = ({i}Π{Γ(i)})^inv(q,δ) = g^({i}Σ{γ(i)}×inv(q,kγ)) = g^inv(q,k), and r = H'(R).
Each participant computes e = H(m), s(i) = k(i)×e + rσ(i).

Zero-knowledge checking: 5a. Each participant randomly generates l(i), ρ(i) ∈ Z(q), computes V(i) = R^s(i)×g^l(i), A(i) = g^ρ(i), {C(1,i),D(1,i)} = Com(V(i),A(i)) and broadcasts C(1,i).

5b. Each participant broadcasts own D(1,i) and proves they know s(i), l(i) and ρ(i) satisfying the computation process of V(i) and A(i). The protocol is aborted if this proof fails. Let V = g^(-e)×X^(-r)×{i}Π{V(i)}, A = {i}Π{A(i)}.

5c. Each participant computes U(i) = V^ρ(i), T(i) = A^l(i), commits {C(2,i),D(2,i)} = Com(U(i),T(i)) and broadcasts C(2,i).

5d. Each participant broadcasts own D(2,i) to open U(i) and T(i), if {i}Π{U(i)} != {i}Π{T(i)}, the protocol should be aborted.

5e. Otherwise, each participant publishes their own (r,s(i)) pair, and the sum of all s(i) is s = {i}Σ{s(i)} = ke + rkx, which could be used to assemble the signature (r,s) and verifiable with the collective public key X.

The importance of the zero-knowledge checking is that an incorrect DSA signature can be used to extrapolate the private key (whether it is a participant’s personal private key or the theoretical collective private key), and the checking described above can prevent the incorrect DSA signature being published when an error is detected.

The following zero-knowledge proof scheme could be used against V(i) in 5b, (i is omitted below):

Prover randomly selects a, b ∈ Z(q), sends α = R^a×g^b to the Verifier.
Verifier randomly generates challenge c ∈ Z(q) and sends to the Prover.
Prover computes t = a + cs mod q and u = b + cl mod q, and sends to Verifier.
Verifier checks whether R^t×g^u == α×V^c.

Discussion of MPC-CMP-DSA

In the above scheme, k is assembled from k(i) randomly generated by each participant and is not directly present during the computation. Thus, the advantages of generating k(i) with deterministic algorithms are apparently limited compared to single-keyed DSA.

The possibility to compute EdDSA in the manner of MPC-CMP

The key to compute EdDSA distributively is to compute R = kG distributively without leaking k.

Can SMPC solve “single point of failure” issue?

From the point of view of the application, e.g: the digital custody needs multiple parties to participate in each operation, even if the attacker compromises one of the participating nodes, this does not lead to the compromise of entire system. At first glance, this solves the problem of a single point of failure for typical “ideal” scenario, but the real-life situation is much more complicated. SMPC cannot solve the problem of a single point of falure in the following scenarios.

Alice, Bob and Chris use Windows, GNU/Linux and Mac OS X to deploy an SMPC scheme, respectively, but meet worst-case scenario, that is, the attacker uses a set of 0day exploits to compromise each node in 1 second by utilizing some sophisticated RCEs.
Only the service node in Tier-4 data center knows the IP address of the participant node and performs MPC operations. Unfortunately, there is a mole using a PCI device which looks like a USB one to conduct a DMA attack to compromise the system in Tier-4 data center, and then performing lateral movement and further infiltration to implant rootkits even bootkits. In this circumstances, any normal operations launched by custodian’s client are able to lead to diaster which scenario 1) can be happened reversely.
Gain the footholds by phishing, then attack the custodian via methods like scenario 1).

Note that security incidents caused by stupid operations of cross-chain bridges are not discussed in the threat model of this article.

Can integration of TEE mitigate the above risks?

No. ALthough CCC (Confidential Computing Consortium) mentioned about enclave/TEE solutions like Intel SGX/AMD SEV to work with SMPC, but the technical analysis of CCC also discussed the risk and defect of these technologies. The failure of Intel SGX is an interesting example and the detail is in our previous write-up Intel SGX deprecation review. TEE can reduce the risk of certain components with proper use, but this is not a silver bullet.

Summary

Don’t roll your own crypto unless you know what you’re really doing.
Double confirm that if SMPC libraries has a real implementation of zero-knowledge proof even in a hardcoded scheme. (Some vendors or open source SMPC implementations doesn’t have ZKP implementation by default)
Follow the cypherpunks/cryptography best-practices, e.g: the risk-based assessment for non-deterministics approach is necessary, etc.
User’s threat model is usually not vendor’s threat model. But vendor’s threat model seems “OK” to user. So make sure the SMPC vendor’s threat model fits yours.
System security & cryptography engineering are twins. If your stupidity intend to ignore one of them, your production system will have serious problem.
The devil is in the details. Technical detail matters!