MPCs going Harder, Better, Faster, and Stronger

by Peyman Momeni (Co-Founder) and Setareh Ghorshi (Cryptography Engineer)

You’ve heard about Multi-party computation (MPC) in many different contexts, ranging from DeFi, gaming, and social, to federated learning.
In this article, we explore MPC and secret sharing. What do parties know? Do they know things? Let's find out.

While MPCs have been researched since the 1980s, they are one of the most misunderstood categories in web3. They are not just threshold signatures; MPC is not even a specific algorithm – it's a problem that many protocols are trying to solve with different security models, efficiency optimizations, and cryptographic assumptions.

Simply put, MPC allows (n) parties to store private inputs and jointly perform computations on them without revealing their inputs to others. When talking about MPC, (n) can be any number, ranging from two to any number of participants desired,e.g. garbled circuits and Renegade are 2PC, WorldCoin is 3PC, and Fairblock and Arcium can be as high as 200PC. Using MPCs, we can solve some of the most fundamental issues in blockchain infrastructure and unleash the next generation of fun and impactful applications on-chain.

Most MPC algorithms such as (

$t\text{IBE}$,

$t\text{FHE}$) and (

$\text{SPDZ}$) are based on secret sharing algorithms. Secret sharing algorithms can be utilized either with a trusted dealer or without trusting any third parties – we use this approach for distributed key generation (DKG). At Fairblock, we have implemented Joint Feldman DKG, which is one of the most widely used DKG schemes nowadays and consists of (n) parallel verifiable secret sharing (VSS) instances. Fairblock’s FairyRing chain uses DKG between its validators to communicate and send messages amongst the network and disincentivize collusion. Moreover, we implemented on-chain verification of the shares for resolving complaints using Non-Interactive Zero-Knowledge (NIZK) proofs for checking the validity of the revealed keys (the keys used for encryption and decryption of the shares). NIZK proofs prevent parties from wrongly accusing each other by publishing invalid keys.

Nevertheless, we are actively monitoring new research in cryptography schemes and adopting new approaches that might enhance the security and efficiency of our system.

For the rest of this article, we’ll describe how secret sharing works in more detail and then present a recent secret sharing scheme, which has

$8.2-25.2x$ faster sharing and

$2.7-23.2x$ faster reconstruction time compared to prior works.

VSS

In a Verifiable Secret Sharing (VSS) scheme, a dealer distributes shares of a secret among (n) parties such that at least (t+1) parties need to combine their shares to regenerate the secret. The verifiability property allows for verification of the received shares by the parties. A well-known VSS scheme is Feldman’s VSS, which is based on Shamir’s Secret Sharing (SSS).

In SSS, the dealer chooses a secret value (s) and constructs a polynomial that has its constant part as the secret value:

$$p(x)=s+a_{1}x+a_2{x}^2+\cdots +a_t{x}^t$$

Then, the dealer calculates the share for each party (i) as:

$$s_i=p(i)$$

Here, the share of each party is the evaluation of the (t)-degree polynomial at a specific point. Hence, any (t+1) parties can aggregate their shares using the Lagrange Interpolation formula to recover the polynomial and then recover (s) by calculating (p(0)). Feldman’s VSS extends this protocol by allowing the parties to validate the shares they receive, which is useful in case the dealer itself is malicious.

For the share validation to be possible, the dealer calculates the following commitments for the polynomial:

$$A_i=g^{a_i}(a_0=s)$$

Using these commitments, each party can verify that the share they received actually comes from the polynomial. Assuming party (k) has share (

$s_k$), they need to check this equality:

$$g^{s_k}=\prod _{i=0}^t{A}_i^{k^i}$$

What can be done to improve the current VSS scheme?

VSS is powerful, but it is also computationally expensive, making it less suitable for applications with many participants. Recent research, such as "Efficient Secret Sharing for Large-Scale Applications" proposes a more efficient scheme for secret sharing by replacing costly polynomial operations with linear equations.

Efficient Secret Sharing Scheme

The mentioned research paper presents a secret sharing scheme based on linear erasure codes. Erasure codes transform an input message into a larger codeword (encoding), such that the original message can be recovered even if parts of the codeword are erased (decoding). This approach constructs its own linear erasure code using random band matrices.

In this scheme, instead of a polynomial, a random band matrix (M) with independent rows and a random vector (x) are generated. The number of rows in (M) is equal to the number of parties (n), and the number of columns is at least the privacy threshold (t).

(M) is generated using the following algorithm:

For each row of (M), a random seed (

${\text{seed}}_i$) is picked. Then, we set

$$\chi =H1({\text{seed}}_i)$$

and

$$b=H2({\text{seed}}_i)$$

(

$\chi$ ) will be the starting position, and (b) will be the value of the row. Meaning that starting from the (

$\chi$ ) position in the row, we set the next (

$w=\text{len}(b)$ ) entries each to one bit of ( b ), and the rest of the entries in the row are set to zero.

Now, assuming we have a secret value (m), first a masking for (m) is calculated as follows:

$$\text{mask}=m+H(x)$$

Then, for each party ( i ), their share is generated as:

$$s_i=M_i\cdot x$$

Accordingly, with matrix-vector multiplication (

$y=M\cdot x$ ), the share of each party ( i ) will be (

$y_i$ ), the result of the (

$i^{\text{th}}$ ) row of ( M ) multiplied by the vector ( x ).

Since the rows of ( M ) are independent, the adversary cannot learn about any row of ( M ) without compromising the corresponding party.

When the parties decide to regenerate the shares, they combine their shares and use Gaussian elimination to solve the resulting set of linear equations to recover ( x ). Then, with ( x ), the actual secret value ( m ) can be calculated using the mask value.

In summary, the secret-sharing process is as follows:

For this secret sharing to become verifiable (Feldman-based VSS algorithm), the commitments in the form of

$$pk\leftarrow [g^{x_1},\dots ,g^{x_t}]$$

can be used. Since each party has their row (

$M_i$ ) and share (

$y_i=M_i\cdot x$ ), they can use the commitments to verify their share by checking this equality:

$$g^{y_i}=\prod _{j\in [t]}{\left(g^{x_j}\right)}^{M_{ij}}$$

where ( t ) is the number of columns in ( M ).

A similar algorithm can be used to construct Pedersen-based VSS using a blinding vector ( v ) along with ( x ) and two generators ( g ) and ( h ). In this algorithm:

$$pk\leftarrow [g^{x_1}{h}^{v_1},\dots ,g^{x_t}{h}^{v_t}]$$

Each share is modified to contain both (

$y_i=M_i\cdot x$ ) and (

$u_i=M_i\cdot v$ ). Then, the verification requires checking the following equality:

$$g^{y_i}{h}^{u_i}=\prod _{j\in [t]}{\left(g^{x_j}{h}^{v_j}\right)}^{M_{ij}}.$$

Using this VSS as the underlying algorithm for MPCs and DKG can improve their performance and unlock endless new opportunities in crypto applications.

Conclusion

Recent research, such as the ramp secret sharing scheme proposed by the mentioned paper, has enhanced the performance of Verifiable Secret Sharing for large-scale applications.

At Fairblock, we are committed to continuously improving cryptographic protocols to stay at the top of technological advancements. The described improvements in secret sharing represent a potential future path for our DKG implementations. We are actively researching such new schemes and adopting them to ensure the efficiency and robustness of our framework.