Cryptography
Protocols
What is multi-party computation (MPC)?
MPC refers to a class of privacy-preserving cryptographic protocols that allows multiple parties (e.g., people, organizations, devices, etc.) to perform joint computations while keeping their data private from each other. This is done by using algorithms and cryptographic techniques such as secret sharing, garbled circuits or zero knowledge proofs to name a few.
The most well-known example in illustrating the capabilities of MPC is the Yao’s Millionaires’ Problem, in which two millionaires meet at a restaurant and start comparing how much money they have without disclosing their wealth to each other. The trick is for each millionaire to send a function of their wealth to a waiter, who then compares the two functions to determine who has the greater wealth without knowing the exact sum of money each one owns.
Generally, MPC protocols can be broken down into three main phases:
1. ✨ The distributed key generation (DKG)
The distributed key generation (DKG) phase during which each party creates a private key share (also known as secret share) and the derived public key. Note that the most recent protocols (e.g., GG18, GG20, CGGMP21) unlike Shamir Secret Sharing Scheme (SSSS), guarantee no single points of failure as each key share is generated separately by each signing party and do not require any single “dealer” in the process.
2. 🔮 The threshold signing (TSS)
The threshold signing (TSS) phase during which each signing party within the threshold group inputs their secret key share as well as the message (e.g., a Bitcoin transaction from Alice to Bob) to a cryptographic algorithm (e.g., Schnorr, ECDSA, EdDSA) from which a signed message is created as the output.
3. 🌟 The zero knowledge proof (ZKP)
The zero knowledge proof (ZKP) phase during which each party sends a message to the others, containing a unique identifier, the signature, and a commitment to the secret key shares. The zero knowledge proof verification is done by having each party exchange cryptographic challenges and responses that are matched against each other in search of a valid commitment, which in turn validates the signature.
______________________________________________________________________________________________________________________
Modern MPC protocols never generate a complete private key on any single device. Instead, they create key shares, also known as "partial keys," which remain within the devices they were generated on. This design approach forms the first layer of defense against single points of failure and associated risks related to key generation, storage, and utilization. By leveraging distributed key sharding properties and autonomous recovery mechanisms, MPC introduces a new design landscape that significantly enhances business continuity with higher fault tolerance and resistance to threats compared to hardware-first setups. It revolutionizes traditional cryptography's security paradigm, which previously relied solely on single points of trust and necessitated substantial emphasis and resources on physical security aspects.
Please note: MPC has gained significant popularity and attention since 2018, as companies in the crypto custody industry adopted efficient papers to enhance hot wallets' security, rivaling cold wallets in some cases, if not surpassing them. This trend led many companies to label their products as MPC-based, while hardware skeptics criticized it to protect their market share. As with most hyped buzzwords, this has led to misrepresentations and misconceptions.
For instance, a prevalent misconception suggests that multi-party computation is a recent discovery. In truth, MPC dates back to the late 1970s, initially explored for remote poker playing and task simulations without third-party involvement. In 1982, Andrew Yao introduced secure two-party computation (2PC) as a solution to the Millionaires' Problem, followed by a more general solution for any feasible computation in 1986. MPC's history is as substantial as Hardware Security Modules (HSMs), introduced in 1972, which played a role in protecting devices with PIN-generating keys. Over the last fifty years, MPC has evolved into a cornerstone of modern key security, with over 10,000 academic papers published and numerous companies integrating it into their products.
Another common misconception is that MPC refers to a single crypto-primitive or a unique protocol, which is not the case. MPC is a cryptographic category encompassing a diverse range of protocols utilizing various primitives. This dynamic domain is continually evolving, with new papers published each week, describing different protocols for diverse applications and features. In your due diligence, it is essential to inquire about the specific MPC protocol a product employs and its purpose, rather than merely whether MPC is used or not.
Definition
Multi-party computation (MPC)
What is a signature scheme?
A signature scheme enables digital message signing and subsequent verification by others to confirm the authenticity of the sender. In the context of blockchains, signature schemes are utilized to validate authorized transactions, ensuring that only the rightful owner of a wallet can initiate fund transfers.
What is a threshold signature scheme (TSS)?
TSS is an important part of MPC and can be viewed as a special kind of MPC for signature schemes. A threshold signature is a type of digital signature that gets validated only if in the signing group a preset of participants knowingly signs together. In a t-out-of-n TSS, n parties each hold signing key shares (which can be viewed as pieces of a signing key) such that any t of those parties can collaboratively generate a signature, but an attacker who compromises up to t-1 of those parties does not have sufficient information to generate a signature.
Threshold signatures have become increasingly popular within information security applications over the past few years because of their unique properties which enable systems to guarantee:
- No single point of failure.
The system resists single-point attacks, requiring attackers to compromise multiple devices for access to the key. - No single point of trust.
Enhanced security through distributed trust prevents any single key shareholder from signing transactions in isolation. - Attack tolerance.
Threshold signatures ensure the system withstands multiple attacks without interrupting signature delivery, as long as the threshold party remains active. - Fault tolerance.
The system maintains signature delivery even with multiple participants temporarily or permanently unavailable within the threshold signing group. - Responsive recovery.
The system offers adaptable recovery options, including repairing specific key shares, refreshing multiple key shares, and rotating the key pair. - Business continuity.
Repairing or refreshing key shares has no impact on the public key or address, ensuring frictionless fund transfers without any disruptions. - Preventive security.
Native key recovery mechanisms can be automated systematically or triggered heuristically, reducing the attack window to a limited time interval.
What is the difference between TSS and Multisig?
Threshold Signature Scheme (TSS) and Multisignature (Multisig) serve similar purposes, enabling secure transaction signing. However, they differ in several key aspects:
- Blockchain Specificity: Multisig is limited to specific blockchains, while TSS operates across all blockchains, offering broader applicability.
- Interaction and Privacy: Multisig may be non-interactive, but it exposes access structure and signers on-chain, compromising transaction privacy and incurring higher gas fees. In contrast, TSS is conducted off-chain, concealing signers' details within regular-looking transactions, providing enhanced privacy and potentially reducing costs.
- Participant Requirements: Multisig necessitates two or more participants to sign a transaction. In contrast, TSS is more secure and flexible, requiring only a preset of all participants, streamlining the process while maintaining robust security.
- Business Continuity: TSS offers a distinct advantage with the ability to refresh private key shares without altering the public key or address. In contrast, Multisig can only rotate the entire key, resulting in a more cumbersome and disruptive recovery process.
In summary, both TSS and Multisig offer distinct advantages in ensuring secure transaction signing. While Multisig excels in providing robust accountability and transactional transparency, it may not be the ideal solution for privacy-sensitive scenarios. On the other hand, TSS stands out due to its exceptional versatility, privacy preservation, and efficiency, making it well-suited for diverse multichain use cases.
What is the difference between TSS and SSS?
Shamir Secret Sharing (SSS) is commonly known to possess a critical single point of failure. In SSS, a key share "dealer" is relied upon in the centralized setting to reconstruct the key at each step of the multi-party computation, assuming trust in this entity. Conversely, Threshold Signature Schemes (TSS), never reconstruct the key by any single signer during the wallet's lifespan, eliminating the single point of failure. To better grasp the distinctions between SSS and TSS, let's focus on the key generation process. SSS assumes the full generation of the key by a single party, which is then split into shares and reconstructed each time for signing. On the other hand, TSS generates the key through distributed key shares, often referred to as 'partial keys.' This unique approach empowers TSS to execute and reassemble partial signatures exclusively, without any single party reconstructing the entire key.
In summary, TSS provides enhanced security and resilience by avoiding reliance on a single entity for key reconstruction, making it a more robust and trustless solution compared to SSS.
Note:
MPC has gained significant popularity and attention since 2018, as companies in the crypto custody industry adopted efficient papers to enhance hot wallets' security, rivaling cold wallets in some cases, if not surpassing them. This trend led many companies to label their products as MPC-based, while hardware skeptics criticized it to protect their market share. As with most hyped buzzwords, this has led to misrepresentations and misconceptions.
Implementation
Is TSS a reliable signature scheme?
Threshold cryptography, akin to MPC, is not a recent subject of research. Back in 1994, Alfredo De Santis, Yvo Desmedt, Yair Frankel, and Moti Yung pioneered a threshold system for a security-proven trapdoor function. Initially, this cryptographic technology found application primarily in organizations safeguarding valuable secrets, such as the military and governments. However, following numerous password breaches on public websites in 2012, RSA Security responded by releasing audited open-source software, making threshold cryptography accessible to all. Consequently, this move propelled wider adoption and heightened awareness regarding the enhanced security of threshold signatures compared to single signatures.
Previously, TSS faced criticism for lacking standardization when compared to HSMs certified by internationally recognized standards like Common Criteria or FIPS-140. This lack raised concerns about independent assurance in product design and cryptographic algorithms. However, this criticism no longer holds ground, as NIST initiated the standardization of threshold systems in 2019. They published a Roadmap Toward Criteria for Threshold Schemes for Cryptographic Primitives, and in January 2023, they launched their first standardization initiative for Multi-Party Threshold Schemes. This initiative aims to establish an official framework that empowers technologists to choose suitable TSS protocols, backed by mathematical security proofs, audited code, peer-reviewed primitives, and pentested design schemes. Note: Dfns’s Chief Scientist Dr. Jonathan Katz and co-author of Threshold Cryptosystems Based on Factoring published in 2001 with Moti Yung (co-inventor of TSS) has been pioneering threshold cryptography for over two decades.
Email research@dfns.co for any additional questions.
Computer Security Resource Center
Roadmap Toward Criteria for Threshold Schemes for Cryptographic Primitives
Contact
Email research@dfns.co for any additional questions.
Where can I find robust TSS implementations?
If you're keen on delving into open-source threshold signature schemes, we highly recommend exploring ZenGo X's curated list of TSS libraries on Github, crafted by their great research team. However, it's essential to exercise caution, as not all libraries are created equal. Before implementing any of them, conducting thorough due diligence is paramount. We advise scrutinizing the library's development team, security models, proofs, algorithms, and any audit reports or certifications granted. These factors contribute significantly to a robust risk assessment. Dfns will soon be open-sourcing an audited CGGMP21 library in Rust.
Library
Curated list of TSS libraries
How does Dfns implement MPC?
Utilizing MPC for key generation and transaction signing in collaboration with external entities enables Dfns to reduce the reliance on social trust, thereby safeguarding sensitive keys and emulating less efficient blockchains with highly decentralized wallets. At Dfns, MPC stands at the core of our decentralized key management network, meticulously operated by top-tier data centers around the world, guaranteeing governance neutrality and the enduring integrity of key generation and signing processes. Nevertheless, it is vital to emphasize that while MPC plays a crucial role in our security system, it is just one component among others. The quality and precision of architectural decisions and technical implementations are equally, if not more, crucial than the mere presence of cryptographic protocols.
Our first product version came out in May 2020 and was based on ZenGo X’s multi-party-ecdsa library. However, ZenGo X (formerly known as KZen) uses a GPL-3 license forcing free software to remain free and to open-source code built with GPL-3-licensed packages. Accidentally failing to do so would have put us into legal trouble, as seen in the Artifex v. Hancom decision.
Therefore, in March 2021, we decided to switch to ING’s threshold signatures library for ECDSA (audited by Kudelski Security in March 2021), and Binance’s tss-lib for EdDSA (audited by Kudelski Security in October 2019) using Rust as the programming language. Both libraries have been developed based on a publication from Rosario Gennaro and Steven Goldfeder: Fast Multiparty Threshold ECDSA with Fast Trustless Setup (also known as “GG18”).
More recently, since September 2022, Dfns has been implementing its own MPC library based on CGGMP21 (i.e., an upgraded version of GG18/GG20 by Ran Canetti et al.) for ECDSA and on FROST for Schnorr-based signature schemes like EdDSA, along with the dependent set of proprietary cryptographic libraries needed to ensure system reliability and autonomy. We look forward to open-sourcing an audited version of our CGGMP21 library sometime in 2023.
If you’re interested in contributing to this project, contact research@dfns.co
How secure is Dfns’s MPC implementation?
In summary, to successfully overcome state-of-the-art threshold security systems, attackers would have to identify the locations of each signer in a threshold group and attack each signer simultaneously within the limited time interval given between two key refresh or rotations. The technical security features and mathematical properties mentioned above are only effective if the key shares are generated across several devices and belong to different key shareholders. Nevertheless, when assuming the above as well as high-standard code implementations, it is fair to say threshold signatures are the most secure digital signature in modern cryptographic literature as they offer unmatched security, availability, responsiveness and business continuity.
Award-winning cybersecurity firm Kudelski Security was asked in 2022 to lead a 3 month-long audit of our current MPC implementations which ended on September 15, 2022. The report was authored by Dr. Tommaso Gagliardoni (PhD in cryptography, ex IBM) who concluded as follows: “In general, we found the implementation to be of high standard and we found very few issues. We believe that all the identified vulnerabilities can be easily addressed. Moreover, we did not find evidence of any hidden backdoor or malicious intent in the code.” Kudelski Security is well-known for having led almost every code audit among the popular open-source threshold signature libraries – from Binance, ING, ZenGo, Thorchain to many others. Our CGGMP21 implementation and its dependencies will be audited by top-tier security audit firms as well.
While the audits we undergo don’t constitute indisputable proofs of security, they do lower the odds of finding vulnerabilities. Also, note that Dfns’s research team is led by Jonathan Katz (one of the most prominent pioneering researcher in threshold cryptography), Nigel Smart (one of the most prominent pioneering researcher in applied MPC), Chelsea Komlo (PhD Candidate in cryptography from Waterloo University, co-author of FROST), Denis Varlakov (MPC engineer and main contributor to ZenGo X’s multi-party-ecdsa library) and Antoine Urban (PhD Candidate in cryptography from Polytechnique, specialized in asynchronous MPC and FHE).
For more information about our audit reports, contact security@dfns.co
For more information about our audit reports, contact security@dfns.co
How is Dfns currently implementing DKG (Distributed Key Generation)?
We employ our proprietary protocol implementation of CGGMP21 for ECDSA keys and FROST for Schnorr/EdDSA keys, bolstered by our custom set of libraries featuring cryptographic primitives and a versatile elliptic curve library. Last, our research team under Dr. Jonathan Katz has recently released a paper titled 'Round Optimal Robust Distributed Key Generation,' which will be seamlessly integrated into the aforementioned protocols to expedite key generation.
Cryptographic protocols
Round Optimal Robust Distributed Key Generation
How does Dfns set its MPC threshold parameters?
Dfns sets its default threshold parameters at 3 out of 5, but it remains flexible and customizable.
In 2022, Dfns Labs released an internal document titled "Threshold Parameter Determination," which delves into the crucial selection of threshold parameters t and n for a threshold signature scheme. In such a scheme, a group of n signers holds shares of a secret key, and a signature can be jointly issued by any combination of t signers. The security, in terms of unforgeability, remains intact as long as no more than t - 1 signers are compromised. The practical question that arises is how to appropriately configure t and n for specific deployments. Within this internal note, we present a comprehensive analysis of the considerations involved in making these choices and culminate with concrete recommendations.
If you’re interested in getting access to our internal note, contact research@dfns.co
What signature schemes does Dfns support?
We offer comprehensive support for various cryptographic schemes, including ECDSA (over secp256k1 elliptic curves), EdDSA, and Schnorr (widely used in Bitcoin). We are actively working on incorporating BLS and Stark (an ECDSA variation) into our system. This lineup enables us to provide support for 95 out of the top 100 cryptocurrencies.
Moreover, our responsiveness to customer needs allow us to accommodate additional schemes based on demand. Whether it's different elliptic curves, distinct signature algorithms, or any other specific requirements, we can implement these changes in less than 30 days on average.
Information
Top 100 cryptocurrencies
Is Dfns using any other type of cryptography?
Yes, we harness cryptography across our entire product by implementing cutting-edge technologies to fortify security. For instance, our peer-to-peer network relies on TLS 1.3 communication channels, while our authentication service is based on WebAuthn 3.0. For key storage, we utilize secure enclaves (AMD, Nitro Enclaves, etc.) in TEEs with multisig capabilities, and backup keys are encrypted using AES encryption. Last, we are also actively engaged in researching quantum-resistant MPC primitives to stay ahead in the realm of security.
TLS 1.3
WebAuthn 3.0
Do you offer any cryptographic materials to your clients?
Yes, our clients access Dfns APIs through passkey-based authentication, creating cryptographic keys on their proprietary devices (phones, laptops, etc.).
However, we refrain from handing over the private key material, even key shares, to most of our clients. This is because many lack the expertise and processes to ensure the stringent security and compliance practices required by Dfns for shared key deployment schemes. Instead, the majority of our customer base relies on our fully-managed key management network, operated by trusted T4/3+ data centers. We consider it our duty to protect clients who may lack in-depth knowledge of secure key management, entrusting the maintenance of this critical infrastructure to our highly certified, audited, and battle-tested SaaS solution.
Nevertheless, certain clients have the ability to securely handle their own keys and might ask for on-prem key deployments. We are able to cater to these requests in order to fulfill specific security, compliance, or regulatory needs. Additionally, we provide enterprise-level backup keys only to subscribers of the Enterprise Plan, as part of enhanced security protocols.
Data Center Classifications
T4/3+
Research
Does Dfns utilize quantum-resistant cryptography?
Not at the moment, but our research team is actively engaged in the internal and collaborative development of quantum-resistant MPC, partnering notably with NIST.