✍️MPC-Threshold Signature Schemes

Multi-Party Computation (MPC) covers a class of algorithms that facilitate varied computation over private data, across multiple parties, without exposing the data itself.

MPC enables a set of parties that do not trust each other, to jointly compute a function over the combination of their individual private inputs. Threshold signature Schemes (TSS) are a special case of MPC where the function to be computed is a cryptographic digital signature, and the private inputs are secret shares of the signing key. In digital signature settings (parties trying to generate indistinguishable signatures when compared to having the private key as a whole in one place), private key shares/shards are the secret data, and digital signature curves-ECDSA & EdDSA-are the compute functions. As such, threshold signatures protocols are multi-step and interactive protocols built through cryptographic primitives and zero-knowledge proofs.

Multi-Party Computation (MPC) as a technology has seen promising growth and wider adoption, in large part due to interest fueled by recent attacks exploiting single points of failure in managing private keys. High-profile failures of centralized entities (like FTX, most recently) have particularly added to the interest in shifting towards decentralized financial products, where user empowerment is of utmost concern.

The history of MPC dates back to the 1980s, when several foundational results [Yao86, BGW88, GMW86, CCD88] established its feasibility. Threshold Signatures Schemes (TSS), an application of MPC with tailored protocols, enjoy broad deployment in enterprise settings today. The protocols of Lindell, GG19, GG20, DKLs18, DKLs19, and CMP to name a few, are used to decentralize key management for the ECDSA Signature Scheme.

In the foundational Bitcoin whitepaper [Bitcoin], Satoshi Nakamoto specified the ECDSA scheme with the secp256k1 curve to be used as the canonical signature scheme for the Bitcoin protocol. This choice has obvious merits — ECDSA produces compact signatures that are fast to generate and verify. In addition, it has withstood decades of cryptanalysis and enjoys wide compatibility across audited libraries. However, its non-linear structure has famously posed a challenge for MPC protocol designers aiming to decentralize its computation.

MPC -TSS Recap

Threshold Signature Protocols vary in complexity depending on the structure of the signature scheme in consideration. They can be:

• straightforward and non-interactive as in the case of BLS (Boneh, Lynn, and Shacham),

• mildly interactive (but technically simple) as in the case of EdDSA/Schnorr, or

• relatively complex, using sophisticated cryptographic primitives such as secure multiplication and zero-knowledge proofs, as in the case of ECDSA.

In general, Threshold Signatures have three phases:

• Distributed Key Generation (DKG),

• Distributed Signing, and

• Pro-activization i.e. Key rotation/refresh.

Each phase has its own distinct set of cryptographic operations and interaction patterns amongst computing nodes that hold shares of the signing key. These nodes can be any device with sufficient computational and memory capability, including smartphones, server nodes, and edge devices.