HackMD
The PSE MPC/FHE Summer Residency 2024
What happened last summer?
The PSE MPC/FHE Summer Residency 2024 in Tokyo is a gathering of PSE members and external experts whom have had close collaboration with PSE in the past months/years. We worked on the following goals, roughly:
- Knowledge Sharing on Foundation of MPC/FHE, where ZK people learn about MPC/FHE, MPC people learn from FHE people and vice versa;
- Demystifying myths around MPC/FHE: what are the bottlenecks of each technique? how are ZK, MPC, FHE related? how can ZK applications benefit from these new techniques? what are the appropriate usecases of MPC/FHE inside/outside blockchain? what are the fundamental requirements when deploying these new techniques?
- Sharing and demonstration of existing MPC/FHE technology/applications;
- Proposal and prelimenary results on new technology/applications;
- And last but not least, to get people to know each other to foster potential future collaboration even in another subject.
In what follow I will try my best to make a summary about what happened during the residency.
Authorship, Acknowledgement and Disclaimers aaa
Note: Take the description in this note with a tiny grain of salt, as (slight) imprecisions are intentionally introduced for the sake of ease of reading and understanding. The whole purpose of this note is to help understanding the notion of generic MPC/FHE, its construction and the existing MPC/FHE software ecosystem. MPC/FHE is a great tool to build privacy-preserving decentralized multiparty protocol such as private Machine Learning Model Training and Inference.
Spoiler Alert
Foundation of MPC and FHE
MPC as a Technique: Garbled Circuit and Secret Sharing MPC
The first topic discussed is the basics of MPC as a Technique: Garbled Circuit and Secret Sharing MPC.
When MPC is discussed among the crowd it is usually generic MPC technique in which we can employ two approaches each with different pros and cons, namely Secret Sharing and Garble Circuit, to implement two generic operations: ADD/XOR and MUL/AND.
Secret Sharing MPC allows the participants to split the secret inputs into shares and send them to the other parties. The assumption on the secrecy of the input depends on whether the sharing scheme is additive (n out of n) or threshold (t out of n). Then the parties can perform computation on the shares. While addition and multiplication by a scalar is free (i.e. can be done locally), multiplication of two secret-shared values requires interaction (1 round), hence the multiplicative depth which scales based on network latency is the complexity of a circuit in this approach.
Garble Circuit MPC consists of two parties called Garbler (G) and Evaluator (E). In GC-based MPC the Garbler G will encrypt (garble) the circuit and send the encrypted circuit C along with its decryption keys (that correspond to G's private inputs but look random to the Evaluator E) and let the Evaluator E obtain its decryption keys (via Oblivious Transfer, that correspond to the Evaluator E's private input but without the Garbler G learning which keys are obtained). Then the Evaluator E can decrypt the garbled circuit C to obtain the final result (and send it back to the Garbler G if necessary). GC-based MPC is constant round so network latency is not an important factor here. The bottleneck in this approach is the size of the garbled circuit C and thus network bandwidth is key to scalability of GC-based MPC.
For more information also see an in-depth description of Garbled Circuit: Primer to GC and Optimizations + (Generalized) Half-Gate Optimization.
Find out more about this talk during the residency: Slides (see the first part) and Videos
Mathematical Foundation and Recent advances in FHE
The second discussed topic is FHE: its foundation and recent advances;
Foundation of FHE
Fully Homomorphic Encryption (FHE) is a cryptographic primitive that allows one to perform arbitrary operation (hence called "Fully") on the FHE ciphertexts without decrypting them (i.e. no decryption key is required during these ciphertext operations). There are different FHE schemes that support different set of operations and also to different extent.
FHE is based on Lattice, in particular the (Ring) Learning with Errors (RLWE),
During the residency we exemplified FHE construction from RLWE with the BFV scheme in this note.
The key to FHE is to understand the notion of noise growth after each multiplication
and the boostrapping process after some multiplications which removes the noise accumulation
The bottleneck of FHE, as opposed to network latency of Secret-Sharing and network bandwith of Garbled-Circuit-MPC, is that FHE requires high computational power. The scalability of FHE relies on development of CPU, GPU and parallelization of computation.
You can also check out this Slides for some additional FHE constructions.
Recent advances in FHE
We are at the 3rd generation of FHE and going forward rapidly:
Actually, very rapidly:
Development of FHE requires solving different challenges (both technical and social aspect); yet we are still strong and moving forward, with challenges being addressed in a timely manner (also ):
Here is another rough benchmark of the state of the art FHE (HEaaN) on real numbers:
Further information of this talk is available: Slides and Videos
MPC as a Paradigm: MPC(GC/SS) + FHE and more …
But MPC is beyond the discussed generic technique (Garbled-Circuit and Secret-Sharing) …
Secure Multiparty Computation (MPC), as it is defined, allows mutually distrustful parties to jointly compute a functionality while keeping the inputs of the participants private.
An MPC protocol can be either application-specific or generic:
While it is clear that Threshold Signature exemplifies application-specific MPC, one can think of generic MPC as an efficient MPC protocol for a Virtual Machine (VM) functionality that takes the joint function as a common program and the private inputs as parameters to the program and the secure execution of the program is within the said VM.
For readers who are familiar with Zero-Knowledge Proof (ZKP), MPC is a generalization of ZKP in which the MPC consists of two parties namely the Prover and the Verifier where only the Prover has secret input which is the witness.
And yes, Fully Homomorphic Encryption is among techniques (along side Garbled-Circuit and Secret-Sharing) that can be used for MPC construction in the most straightforward mental model:
That said, MPC is not a primitive but a collective of techniques to achieve the above purpose. Efficient MPC protocols exist for specific functionalities from simple statistical aggregation such as mean aggregation (for ads), set intersection (PSI) to complex ones such as RAM (called Oblivious-RAM) and even Machine Learning (ML).
As each technique GC/SS/FHE and specialized MPC has its own advantage, it is typical to combine them into one's privacy preserving protocol for efficiency:
How MPC/FHE interplay with Blockchain/dApps?
With respect to ZK, MPC and FHE are useful in the sense that they enable truly multiparty private applications:
Find out more about MPC as a paradigm: Slides (see the 2nd part) and Videos
When to Which: A practioner's guide to MPC(GC/SS)/FHE
First off, we need to understand what are we talking about when we say resource requirement in a cryptographic protocol, they are: computational power; network bandwidth, latency; and last but not least, the liveness requirement of the participants:
In terms of resource availability, FHE truly shines when we have access to high computational power such as GPUs (many of them), FHE is non-interactive meaning there is (almost) no communication requirements (such as network bandwidth and latency) when deploying FHE (liveness is high due to the operations can be done by any public entity). FHE is very suitable for building highly scalable consumer facing applications where high computational power is available at a central party (i.e. the service provider).
For readers from the cybersecurity world, FHE protects data in compute (as opposed to data at rest and in transit).
It is only tricky when we have to answer the question "Who has the decryption key?". Multiparty FHE solves this by sharing the decryption key among a committee and assume honest majority for liveness and privacy.
On the other hand, Secret Sharing based MPC shines when network latency is not an issue (i.e. low latency network is available to the participants). Secret Sharing based MPC requires very low computational overhead but liveness is a bit of the problem as everyone has to stay online during the MPC computation.
Luckily, clients (if we have many of them) can delegate their secrecy to a set of committee and assume honest majority for liveness and privacy (as in "Who has the decryption key?" of FHE). 
Last but not least, Garbled Circuit is a middle ground between SS and FHE. Garbled Circuit requires high computational power (not as high as FHE) but its concrete computational complexity is low due to its usage of symmetric cryptographic primitives such as fixed-key AES which is supported by most modern CPUs natively (AES-NI). Garbled Circuit requires a constant number of rounds hence latency is not a deployment requirement. As such GC also offers high liveness. However, Garbled Circuit based MPC transmit an abundant amount of data therefore a high bandwidth network is very much desirable.
To conclude, FHE is more suitable for replacing the high scale execution of a central party in clear with ciphertext operations for privacy. In such case the central party is assumed to have access to high computational power and privacy relies on honest majority of the key committee. Secret-sharing MPC is more or less in the same situation, it is less costly but not as scalable as FHE due to capping on network latency is hard to break (while FHE relies on significant advances in computational power, i.e. Moore's Law). Finally Garbled Circuit MPC is more relaxed on computational power and network latency requirement, but is capped by network bandwidth and can be considered as a middle point between FHE and SS-MPC.
Find out more and learn when to which GC/SS/FHE: Slides and Videos
Existing MPC/FHE and some miscs
The curious case of Iris Matching (Realworld MPC)
The MPC Iris Matching project aims to build a Decentralized (Unique) Iris Database using MPC: its two key functionalities are (1) Iris Storage and (2) Similarity Check upon new Iris Registration.
The project employed Secret-Sharing MPC and encountered difficult technical issues to overcome, namely mixed operations, large data sizes and communication overhead:
The project relies on Replicated Secret Sharing and Shamir Secret Sharing techniques each with its own advantages for different purpose (doing arithmetic computation or doing comparison or just to save storage and commnunication or for some security requirement).
The experimental results show feasibility and scalability especially when one considering using Secret Sharing technique with GPU and gives it direct access to network to remove the CPU as a bottleneck.
Privacy Preserving Statistics with MPC-Stats
MPC-Stats is building a platform where a client can query for statistics concerning two or more private datasets without the data owner losing their data privacy (which could be valuable to them).
The project started with ZK-Stats using EZKL
And eventually became MPC-Stats using MP-SPDZ (Secret-Sharing MPC) (and going forward to be FHE-Stats in the next explorative step)
TLSNotary and its MPC tooling: mpz and mpz-play
TLSNotary is an open-source protocol that can verify the authenticity of TLS data while protecting privacy.
TLSNotary has a long history of development (including heavy revamps):
TLSNotary greatly exemplifies the usage of semi-honest Garbled Circuit in realworld application: TLDR and roughly; the Prover and Verifier split the TLS key into two parts and use GC for TLS operations:
Behind the scene, TLSNotary uses mpz which is also a PSE in-house Garbled Circuit library.
If you are interesting in having a taste, you can try out mpz with mpz-play.
TODO PADO?
Play with the Max Pick Challenge
Yes, Max Pick Challenge is an intended pun (MPC).
The Max Pick Challenge is an on-chain guessing game served as a demonstration of co-circom, a collaborative zk-SNARKs tooling effort using circom as a DSL and Secret-Sharing MPC as the backend.
co-circom chooses circom DSL for its popularity and easy usage:
The workflow of co-circom consists of two main parts, namely (1) witness-generation with MPC (Secret-Sharing, also Rep3 and Shamir) and (2) co-zkSnarks generation using the extended witness generated in the first part:
Find out more: Slides and Videos.
Another potential co-circom usecase is Encrypted Scholarship.
FHE-based Oblivious Message Retrieval
Oblivious Message Retrieval (OMR) is a cryptographic protocol that allows a service provider to compress the list of messages intended for a client from a larger list of messages (i.e. generating a digest) without learning anything. The state-of-the-art OMR relies on FHE: 
OMR is particularly useful in privacy-preservation payment network such as zcash:
During the residency we also got some good preliminary result that shows feasibility:
New Proposals and Challenges: MPC/FHE to the Moon
On MPC-fying MACI
Minimal Anti-Collusion Infrastructure (MACI) is an on-chain voting protocol which protects privacy and minimizes the risk of collusion and bribery. Further information about MACI is available on its website.
MACI faces some weaknesses one of which is the central coordinator and the goal of MPC-MACI is to replace this central coordinator with an MPC protocol: 
MPC-MACI relies on several specialized components (ZK and Secret-Sharing MPC)
Other than that MPC-MACI introduced the notion of keychain that is useful for preventing coercion 
Find out more: Slides; most recent keychain/MPC-MACI
Approximation/Greedy Algorithms in MPC-Optimization
Approximation/Greedy Algorithms are often replacements of exact algorithms when one design MPC protocol to solve complex problem due to their flexibility is scalability, i.e. approximation/greedy algorithms focus on adjusting the initial feasible solution to a more optimal solution after each iteration, and the number of iterations can be a parameter for MPC efficiency (computation can be cutoff in the middle based on running time constraint yet we still have somewhat optimal solution).
One prominent example of MPC-Optimization is Distributed Block building via Secure Knapsack Auctions:
The technique of choice is Secret-Sharing MPC
The latest benchmark shows some feasibility:
We have available the Slides and also an extended version.
New MPC Tooling and Better Programmability: MPC-VM
Besides co-circom, there have been other MPC tooling effort introduced at the residency, one of them is CircuitScript, a language for collaboratively "summoning" computations (The circuits generated by Summon are intended for MPC. When performing MPC, you use cryptography to collaboratively compute the output of a function without anyone seeing each other's inputs or any of the intermediary calculations. It's like summoning the result with magic.).
You can learn more about CircuitScript from the [Videos] and some exercises
More than a langauge, there is a collaborative effort formed during the residency for building MPC-VM. The fundamental difference when building a VM is to escape the circuit model of computation and enter the realm of RAM computation which is more natural for general purpose machine, but of course building an MPC RAM Machine is harder than one for circuit:
There are different approaches in the past that we can learn from (inside and outside of cryptography, also in compiler and programming language or even hardware design)
See more in Slides on MPC-VM and Videos
Categorical Theory and Proof of Construction/Protocol Correctness
Categorical Theory and in particular the Yoneda Lemma allows abstraction of FHE (and potentially other cryptographic algorithmic categories) into a generic one with which we can modularly capture and reason about the correctness of the newly constructed protocol:
The Yoneda Lemma is on homomorphism 
and in the case of FHE it captures the following homomorphism 
Find out more: Slides
NFC + MPC/FHE
Cursive, during the residency, performed a demonstration of NFC social applications of MPC, using jiff.
The application allows a participant to register an identity (stored inside the NFC ring) to the Cursive website and then participating in interesting activities such as contacts matching using 2PC-PSI and Fruit Racing.
Screenshots of applications:
Lattice-based Proof System and Verifiable FHE
FHE is a great technique for building privacy preserving consumer facing apps, yet FHE currently falls short to verifiability. It is of urgent need to develop Verifiable FHE which allows clients to encrypt their private inputs, got them sent to the service provider, and got returned a result ciphertexts along side with some verifiable proof. As FHE is based on Lattice, it is natural to choose Lattice-based Proof System for Verifiable FHE:
Honorable Miscs
HERE WE PUT SOME BULLET POINTS WITH SOME BRIEF DESC AND LINK
