Introducing Zama’s Threshold Key Management System (TKMS)

This article was co-authored by Kelong Cong, Morten Dahl, Daniel Demmler, Frederic Egmorte, Tore Frederiksen, Nigel Smart, Maksym Surzhynskyi, and Titouan Tanguy.

‍
Zama's technology enables private computing on encrypted data through Fully Homomorphic Encryption(FHE). However, a major issue in any application is key management – specifically, how to secure and manage the secret keys used to decrypt data. 

To address this, our team at Zama has built a Threshold Key Management System (TKMS) powered by threshold cryptography. Namely, instead of relying on a single party to hold a full decryption key, the key is split into shares, which are generated during a threshold key generation ceremony and distributed among multiple parties. These shares are never recombined during cryptographic operations and meaningful operations with them can only be carried out if more than a threshold number of parties agree to it — similar to how Multi-Party Computation (MPC) wallets work in the blockchain world.

What is the TKMS?

The TKMS is built on top of a secure and robust MPC protocol that supports key management of virtually any FHE scheme. While our implementation is optimized for TFHE (to be used with the fhEVM for private smart contracts), the underlying MPC system is general enough to be adjusted to work for other types of FHE keys, such as those used in the BGV and BFV schemes. 

This week, Zama is making available three key resources which underpin our TKMS technology:

• An open source MPC library which implements all of the threshold operations within the Zama TKMS. 
• A KMS application and interface around the MPC library, which allows the management of key material and authenticated interaction with the underlying library, including a sample client application to interact with a deployed KMS.
• A comprehensive cryptographic report which gives a formal description of the various cryptographic protocols underlying the MPC technology implemented. This document is a draft version of what the Zama team intends to submit to NIST as part of their future threshold cryptography call.

About the codebase

The KMS is a Rust library which implements the MPC algorithms for the TFHE scheme used in Zama products, covering:

• Threshold decryption
• Threshold key generation
• Key resharing 

Additionally, it includes the code to implement a protocol for common-reference string (CRS) generation, for the CRS used in the zero-knowledge proofs of knowledge (ZKPoKs) within Zama’s TFHE-rs library, and the code for threshold decryption and key generation for simple versions of the BGV and BFV encryption schemes  — even if those are not used in Zama’s products.

Alongside, the repository contains a service wrapper around the core MPC primitives, providing management capabilities of key material and rate limiting of accesses via a gRPC interface.

Adaptability & Performance

The library implements various options (for both feasibility and efficiency reasons) for this MPC system, depending on the number of parties and the associated threshold: 

• When the number of players is small (roughly less than 18) we use a protocol which requires a threshold of [.c-inline-code]t<n/3[.c-inline-code];
• When the number of players is larger, we use a protocol which requires a threshold of [.c-inline-code]t<n/4[.c-inline-code]; 

Here, [.c-inline-code]t[.c-inline-code] represents the number of bad players which the protocol can tolerate. 

The MPC protocols are based on Shamir Secret Sharing over Galois Rings, and provide robust protocols, i.e. ones which provide Guaranteed Output Delivery. In layman's terms, if less than or equal to [.c-inline-code]t[.c-inline-code] parties are malicious, a correct output result will always be recovered by the other honest parties. 

Interestingly, when the total number of parties is small, our threshold decryption protocol requires a single round of communication, making it suitable to work over a wide-area network (WAN) where the round trip time between parties may be significant. For example, threshold decrypting up to 2048 ciphertexts takes less than a second when the protocol is run with ten parties. 

The most expensive part of the entire protocol suite is, by far, the key generation, which only occurs once during the protocol setup phase. However, Zama's implementation is highly parallelized such that it can be scaled horizontally if needed. 

Finally, the different building blocks that make up the threshold key generation and threshold decryption can be reused independently, such as for research purposes. In the repository, users will find instructions on how to run our software and produce benchmarks for their own installation.

The protocol report: A deep dive into MPC

Alongside the library, we’re releasing a 250+ page technical report that formally describes the mathematics and protocols behind our MPC stack. This includes: 

• Implementation of threshold cryptography for TFHE, which is supported in Zama products. 
• Implementation of threshold versions of two other popular FHE schemes – BGV and BFV. (Note that these two schemes are currently only experimentally supported in our code base.)
• An explanation of how threshold decryption and key generation are performed, as well as key resharing. 
• Description of three different Zero-Knowledge Proof techniques verifying that a given fresh FHE ciphertext has been correctly encrypted (only two of these techniques are currently implemented in the TFHE-rs library).
• Protocols for the CRS generation needed to implement the vector-commitment based ZKPoKs.

To keep the document approachable, we’ve focused on simplified versions of the TFHE, BGV and BFV schemes. 

A call to the community

At Zama, we strongly believe in open source innovation. By sharing both our code and research, we aim to foster collaboration, transparency and progress in the field of FHE. 

We invite researchers, developers and cryptographers to explore and experiment with these resources, and share with us any feedback: 

• 📧 Email us at hello@zama.ai 
• 🗣️ Join the conversation on fhe.org Discord.
• 💬 Contact the authors of the report directly

‍