This is a follow-up investigation of our PPD Project Plan back in Jan 2025. PPD = Private Proof Delegation Recall that we are in the situation where a weak client, who holds some secret witness to a (public) statement, would like to generate a (public verifiable) zero-knowledge proof of the knowledge of the witness (and that it satisfies some relation), but not able to do so, due to resource constraint such as low computational power, shortage of power (battery life), or low memory. While computational power or battery life are somewhat reasonable to circumvent, memory cap remains a hard constraint of such weak client. In such a situation, the weak client, would like to find a way to delegate the proof generation to a strong server, while, at the same time, would like to keep the witness its own secret. We call such service "Private Proof Delegation; and our team embarked on the quest to fulfill the wish of the client. Existing PPD Solution

Introduction Secure Multiparty Computation (MPC) allows $n$ parties $P_1, \ldots, P_n$ to securely evaluate a joint function $f(x_1, \ldots, x_n)$ while keeping the secret input $x_i$ private to its owner $P_i$. MPC comes with two main flavors of security, namely Semi-honest and Active Security: Semi-Honest (SEM} only guarantees security if the adversary acts according to the protocol, i.e., one will not deviate from the protocol but only tries to break privacy from the MPC transcript that is available to it; Active Security (ACT) is a stronger security setting than SEM that guarantees the security of the MPC protocol even if the adversary acts arbitrarily. Generic MPC is enabled through two approaches: Secret-Sharing (SS) and Garbled-Circuit (GC). We focus on the latter due to its attractive property of constant round complexity (where round complexity is an important factor for blockchain model due to bottleneck in block generation time.) Efficiency of Actively Secure Garbled Circuit. ACT for GC is trivially available through the usage of Zero-Knowledge-Proof, yet even with optimizations, it is necessary to prove a statement with 19 clauses conjunction per gate. Cut-and-Choose is another approach for ACT in which the Garbler prepares $k$ circuits in total, and the Evaluator can choose $t$ to test and only accepts if all $t$ circuits are valid. Yet the preparation of many circuits and the testing for validity yield concrete inefficiency and become unreasonable when the circuit size is large. Another approach is through Authenticated Garbling, which will be our focus due to its efficiency compared with the previous two.

Circom-MPC is a PSE Research project that enables the use of the Circom language to develop MPC applications. In this project, we envisioned MPC as a broader paradigm, where MPC serves as an umbrella for generic techniques such as Zero-Knowledge Proof, Garbled Circuit, Secret-Sharing, or Fully Homomorphic Encryption. Throughout this research the team produced some valuable resources and insights, including: Implementation of circom-2-arithc, a fork of the Circom compiler that targets arithmetic circuits, which can be fed into any MPC backend Example integration of circom-2-arithc with the popular Secret-Sharing based backend MP-SPDZ in circom-MP-SPDZ. Proof of concept application using MPC-ML with keras-2-circom-MP-SPDZ which extends keras-2-circom-ZK to keras-2-circom-MPC. Modular Layer benchmarks for the keras model. We decided to sunset the project for a few reasons:

This is a WIP. Some materials we use for below notes: Summary of FHE Slides [1] Summary of FHE Blog [2] FHE survey paper 2022 [3] Intro to FHE Video [4] CHIMERA [5] KPZ22 [6] shows concretely many important formula in the Appendix

WIP Materials TACEO's MHEGA blog [1] Blind zk-SNARKs paper 2024 [2] Diagonal Method in 4.2 [3] Method 1 ("No-FFT" + No Bootstrapping FHE + Diagonal Method) Just do DFT in the FHE way

In this research we aim at combining Authenticated Garbling and VOLE-in-the-Head techniques to make Garbled Circuit publicly verifiable. We are working on a prototype of our protocol in C++ which put together the code base of emp-ag2pc (Authenticated Garbling) and faest (VOLE-in-the-Head). Introduction to Garbled Circuit Garbled Circuit (GC) protocol 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. Screenshot 2024-08-16 at 10.01.33 For more information also see an in-depth description of Garbled Circuit: Primer to GC and Optimizations + (Generalized) Half-Gate Optimization.

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.

See below. Writeups (some required signed-in) GeneralIntro to Garbled Circuit Garbled Arithmetic Circuit Residue Number System and Applications Beyond the Circuit Model: challenges in Circom Extension Notes on Authenticated Garbling Applications