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

[Karl Semich]

It’s nice to see the article style although the content is above the
product of my expertise, interest, and attention soan, leaving the
topic still mystifying for me. I can’t verify if it’s a fake or an
honest share, but it’s a breath of fresh air.

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 khe
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.

Shamir’s Secret Sharing

Split a secret value x on GF(q) into n pieces. x could be restored
when collecting t+1pieces (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.

The property of Shamir’s Secret Sharing

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^3satisfying 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 == Bwith
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” kdeterministically 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!

References

A Technical Analysis of Confidential Computing v1.3

https://confidentialcomputing.io/wp-content/uploads/sites/85/2023/01/CCC-A-Technical-Analysis-of-Confidential-Computing-v1.3_Updated_November_2022.pdf

A Pragmatic Introduction to Secure Multi-Party Computation

https://securecomputation.org/docs/pragmaticmpc.pdf

Next Generation Data Center Security: The Cornerstone of Web3?

https://hardenedvault.net/blog/2022-08-05-next-gen-data-center-web3/

Intel SGX deprecation review

https://hardenedvault.net/blog/2022-01-15-sgx-deprecated/

Firmware bootkits

https://github.com/hardenedvault/bootkit-samples

Taurus Releases the First Open-Source Implementation of MPC-CMP

https://blog.taurushq.com/first-open-source-implementation-of-mpc-cmp/

Introducing MPC-CMP: Pushing MPC Wallet Signing Speeds 8X

https://www.fireblocks.com/blog/pushing-mpc-wallet-signing-speeds-8x-with-mpc-cmp-9/

QREDO

https://www.qredo.com/qredo-yellow-paper.pdf

Common Terminology for Confidential Computing

https://confidentialcomputing.io/wp-content/uploads/sites/85/2023/01/Common-Terminology-for-Confidential-Computing.pdf

SLIP-0039 : Shamir’s Secret-Sharing for Mnemonic Codes

https://github.com/satoshilabs/slips/blob/master/slip-0039.md#slip-0039--shamirs-secret-sharing-for-mnemonic-codes

TinySMPC

https://github.com/kennysong/tinysmpc