Two millionaires started a competition. They want to compete who is richer but not revealing their actual wealth. Without any trusted third parties, what should they do?

By：Max He，Safeheron Chief Scientist

In 1982, Andrew Chi-Chin Yao, Turing Award winner, introduced a very important concept — Secure Multi-Party Computation in his paper. To vividly explain this concept, he proposed the famous “Millionaire Problem”.

Two millionaires bumped into each other and they are interested in knowing who of them is richer but not revealing their actual wealth.

This paper written by Yao pioneered a vital field — Secure Multi-Party Computation. Now let us reveal Secure Multi-Party Computation for you.

What Is Secure Multi-Party Computation

Secure Multi-Party Computation focuses on how to securely compute a consensual function without any trusted third parties. Secure Multi-Party Computation has been the cryptographic foundation for e-voting, threshold signature, online auctions, etc. Secure Multi-Party Computation in short is generally called SMPC or MPC.

Security of Secure Multi-Party Computation

If an MPC protocol is secure against an attacker with limitless computing power, then it’s deemed as information-theoretic security or unconditional security. If it is secure against an attacker who is limited to polynomial-time computations, it is regarded to be cryptographically secure or conditionally secure.

Types of Technologies Involved in Secure Multi-Party Computation

There are many technologies involved in MPC, such as Garbled Circuit came up with Yao, Oblivious Transfer, Zero Knowledge Proof, Homomorphic Encryption, and more. We will gradually give introductions to those technologies in our Blog.

Key Features of Secure Multi-Party Computation

Input Privacy

MPC studies how to protect the private data of each party during participants’ collaborative computing, focusing on the privacy and security issues between the parties. In the process of Secure Multi-Party Computation, it is necessary to ensure that each party's private input is independent and no local data is leaked during computing.

Computing Accuracy

Multiple computing participants perform the collaborated computing for a certain consensual computing task via the agreed MPC protocol. After all the computing is completed, each party gets the correct data feedback.

Decentralization

Traditional distributed computing is to have the central node coordinate each user’s computing progress, collecting each user’s input. But MPC provides a decentralized computing scheme in which all participants are equal without privileged parties or third parties.

Secure Multi-Party Computation Scenarios in Multisignature

Distributed Private Key Shard Generation

In the traditional generation of the private key, a public-private key pair is generated that the public key is shown to the public as the asset account and the private key is managed by privileged people. Distributed private key shard generation is completely different from traditional private key generation. The private key is no more to be generated locally by a single person. Instead, all participants execute an MPC private key generation protocol in accordance with the preset t/n threshold. When the protocol ends, everyone can get the respective private key shard and a shared public key. This public key is the asset account but the corresponding private key never appears. Thus, the assets under the public key are co-managed by all parties. When the key sharding completes, everyone can hold one private key shard. That’s to say, in order to get the original real private key, the attacker has to obtain the private key shards (no less than the threshold) to recover the real original private key.

Distributed Private Key Refreshing

To enhance security, a key refresh protocol will be executed once in a while and a set of key shards will be refreshed. Once the refreshing protocol is finished, everyone will get a new private key shard and the old one will be invalid.

Distributed Private Key Shard Signature

To obtain a valid signature and thus create a valid single-signature transaction, the MPC Multisignature Protocol must be executed jointly by a threshold number of participants (a quorum). When the protocol is completed, all will get the same valid signature. No private key shard will be exposed during the whole execution.

Common MPC Multisig Protocol

In MPC Multisig, we need to implement various MPC protocols in accordance with different user scenarios, including but not limited to:

  • MPC-ECDSA Protocol
  • MPC-EdDSA Protocol
  • MPC-BLS Protocol
  • MPC-Schnorr Protocol
  • MPC-HMAC Protocol

First to introduce is the MPC-ECDSA Protocol. As most blockchains adopt the ECDSA, based on the elliptic curve Secp256k1, as their signature algorithm, so MPC-ECDSA Protocol catches the most attention among all MPC protocols. The implementation difficulty of the Ecdsa multi-party protocol is obviously higher than other signatures, thus, it takes a very long time for MPC-ECDSA Protocol implementation.

The quickest protocol to get a breakthrough is the Two-Party ECDSA Protocol. Lindell suggested one pretty good two-party MPC protocol (refer to Fast Secure Two-Party ECDSA Signing). One typical implementation of this protocol is ZenGo’s Keyless wallet. Another implementation of the Two-Party MPC-ECDSA Protocol is to apply the Garbled Circuit introduced by Andrew Chi-Chin Yao and Unbound Security has implemented the solution based on this.

Straight after the above, we see progress on the MPC-ECDSA Protocol in the field of common threshold signature. Critical contributors include Gennaro and Goldfeder, Lindell, Doerner and Canetti.

With the above people’s contribution, companies with cryptography competence started to implement their own algorithms. A new era begins!

With more and more new blockchains and applications joining, people have more needs regarding MPC multisignature protocols, including but not limited to MPC-EdDSA Protocol, MPC-BLS Protocol and MPC-Schnorr Protocol. Compared to the ECDSA protocol, corresponding MPC protocols based on signature algorithms such as EdDSA, BLS and Schnorr can be a bit easier, however, we still need to be cautiously careful about implementation as a lot of security traps need to be avoided.

Besides, if managing assets over multiple platforms in one place, people need more protocols, such as MPC-HMAC Protocol. There are serious performance issues in the implementation of the MPC-HMAC Protocol which needs to be optimized several times.

Safeheron And MPC

To satisfy needs for various MPC multisig protocols, to have algorithms applicable to multiple platforms (e.g. Windows, Linux, macOS, Intel® SGX、Android, iOS, and WASM), Safeheron self-developed a series of basic cryptography algorithm libraries, inviting all parties to review their security.

Conclusion

MPC-based Multisignature technology only has one concept of one single private key on the chain that through cryptography, the single point of failure (SPOF) on the private key is thoroughly eliminated. From beginning to end, the single private key never shows up. With multiple private key shards, different parties can compute the final signature via MPC protocol when signing. And the final signature can be verified by the corresponding single public key.

This is the technology called MPC Multisignature. And, as a new generation signature technology, MPC Multisignature is getting more and more crucial. Safeheron will continue to make our efforts and contribute to the MPC field.

Disclaimer: As a blockchain information platform, the articles published on this site represent the personal views of the authors and guests, and have nothing to do with Web3Caff's position. The content of this article is for information sharing only, and does not constitute any investment advice or offer, and please comply with the relevant laws and regulations of your country or region.