MPC, FHE, DP, ZKP, TEE and where Partisia Blockchain fits in
Guest blog from Anders Dalskov, PhD, Cryptography Scientist — Partisia.
The point of this document is to provide the shortest (and most intuitive) possible introduction to each of the technologies mentioned in the title. I hope I succeed in this endeavor.
The technologies in this document all — with exception of Differential Privacy — deal with “secure” computation on data. At a very high level, this means they can be used to perform an arbitrary computation on one or more pieces of data, while keeping this data private.
Secure Multiparty Computation (MPC)
Secure Multiparty Computation, which is what we do here at Partisia, is the term for a fairly broad class of protocols that enable 2 separate entities (called parties) to compute a function, while revealing nothing except the output.
An MPC protocol typically proceeds in three phases: First the inputters secret-share their private inputs. This step can be thought of as each user sending a special type of encryption of their inputs to the nodes doing the computation. The encryption ensures, for example, that at least 2 out of 3 nodes are required to recover the input, and thus, we get a security model that relies on non-collusion. It could also be the case that all 3 nodes must collude to recover the input — in this case, we have a full threshold model (since all servers must collude to break privacy).
The next step involves the nodes (the servers A, B, and C) performing the computation on the encryptions (i.e., secret-shares) received in the input step.
When the nodes finish the computation, they will hold a secret-sharing of the output. Each node’s share is returned to the users, so they can recover the actual output.
As might be inferred from the figures above, MPC works particularly well if the computation nodes are well-connected. Indeed, what makes MPC expensive to run is all the data that the nodes have to send between each other.
MPC have been actively studied in academia since the early 80’s and there are a lot of good resources available to learn more about it:
- Simple explanation of how secret-sharing can be used to keep stuff secret
- Slightly more dense, but also still informative introduction to MPC
- Serious of blog posts that go through many of the aspects of MPC
Fully Homomorphic Computation (FHE)
Fully Homomorphic Encryption (FHE) solves a very old problem: Can I have my data encrypted and compute on it too? FHE is a tool that allows us to not only store data encrypted on a server, but which allows the server to compute on it as well, without having to decrypt it at any point. An illustration of an FHE system is shown below:
In the figure above, a user encrypts their private data and uploads it to a server. However, unlike a traditional E2EE (End-to-End-Encrypted) scenario, the server can actually perform a computation on the user’s private data — directly on ciphertext. The result can then be decrypted by the user using their private key.
FHE, unlike MPC, relies on clever cryptographic computation, rather than clever cryptographic protocols. On the one hand, this means FHE requires less data to be sent between the server and client compared to MPC. On the other hand, FHE requires a lot of computation to be done by the server.
Practically speaking, FHE is slower than MPC (unless we have an incredibly slow network, or incredibly powerful computers).
Practical FHE is a relatively new technology that only came about in 2009. However, since then it has received quite a bit of interest, especially from “bigger” players like Microsoft or IBM.
Partisia Blockchain supports FHE solutions.
Zero-Knowledge Proof Systems (ZKP)
While both MPC and FHE allow us to compute anything, Zero-Knowledge proof (ZKP) systems allow us to compute proofs. In short, ZKP allows us to compute functions where the output is either “true” or “false”.
ZKPs are incredibly popular in the blockchain space, mainly for their role in “rollups”. The particular type of ZKPs used for rollups are ZK-SNARKs, which are succinct proofs. In a nutshell, a succinct proof is a proof whose size is some fixed (small) constant, and where verification is fast. This makes smart particularly useful for blockchains since the proof and verification are both onchain.
That said, ZK rollups don’t actually use the zero-knowledge property — they only use the soundness and succinctness properties of the proof scheme.
Soundness simply means that it is very difficult to construct a proof that appears valid, but in actuality is not.
ZKPs, like FHE, takes place between a single user and a verifier. The user has a secret and they wish to convince the verifier about some fact concerning this secret, without revealing the secret. ZKPs don’t designate a particular verifier, so anyone can usually check that a proof is correct. An illustration of a usage scenario of ZKPs is shown below.
Trusted Execution Environment (TEE)
The final private computation technology I will talk about here is Trusted Execution Environments. A trusted execution environment, or TEE, is basically just a piece of hardware that is trusted to do the right thing. If we trust this particular type of hardware, then private computing is clearly doable, as shown below.
TEEs, being hardware, are tightly connected to some hardware vendor. Often when TEEs are mentioned, what is really meant is something like Intel’s SGX or ARM TrustZone. SGX is the TEE used by Secret Network, for example.
The security model of TEEs is fairly different compared to the other technologies I’ve written about so far, in that it is a lot more opaque. Vulnerabilities have been demonstrated in different iterations of different TEE products, especially SGX.
Differential Privacy (DP)
Differential Privacy is radically different from the previous technologies. (In this discussion I will exclude ZKPs since it does not allow general computations.)
While MPC, TEE and FHE all provide means of computing something on private data, they do not really care about what that something is.
For example, it is possible (albeit pointless) to compute the identity function using both MPC, TEE and FHE.
This is because MPC, TEE and FHE allow us to compute anything. In particular, they allow us to perform computations that aren’t really private.
At this point, we may ask: Well, why would we perform such a silly computation on private data? For some computations, it might be easy to see that it is not private (in the sense that the original input can easily be inferred from the output). However, there are many computations that are seemingly private, but which can also leak the input if we are not careful. For example, it has been shown that it is possible to extract Machine Learning models, simply by querying a prediction API. In another example it was shown that it is possible to extract the data that a model was trained on.
These issues all arise because there are no restrictions on the computation that is performed. Differential Privacy tries to fix this.
Differential Privacy is used to provide a fairly intuitive guarantee. Suppose we are given two databases A and B. The only difference between these two databases, is that a particular entry R exists in A but not in B. Differential Privacy now states that, no matter which type of query we make on the database, we will not be able to guess whether we are interacting with A or B.
Naturally, this means that some queries cannot be allowed. For example, it is not possible to obtain differential privacy if one can simply ask “Is record R in the database?”. Generally, Differential Privacy is obtained by adding noise, or synthetic data, to the database as well as restricting the type of queries that are allowed.
What makes differential privacy different from MPC, TEE and FHE, is that Differential Privacy makes guarantees about the output of a computation, whereas MPC, TEE and FHE makes guarantees about the process of arriving at that output. In summary:
- MPC, TEE, FHE: Nothing is revealed except the output.
- DP: The output does not reveal too much.
This also means that Differential Privacy is not in direct “competition” with MPC, TEE or FHE, but rather complements them.
Conclusion
Attached below is a comparison chart showing how Partisia Blockchains MPC compares with other technologies described above. While each technology has its specific advantages and use cases, it is our feeling that Partisia Blockchain’s MPC, backed by 30+ years of research and practical implementation does seem to provide the most overall coverage of all possible scenarios with very little drawback.
