# General Grant Proposal: Authenticated Garbling * **Project:** MPZ - authenticated garbling ## Project Overview ### Overview This project aims to implement authenticated garbling ([WRK17a](https://eprint.iacr.org/2017/030), [WRK17b](https://eprint.iacr.org/2017/189)) in MPZ. This will complement PSE's ongoing effort to extend MPZ for supporting malicious security. ### Short Rationale Authenticated garbling and its optimizations achieve stronger security guarantees over semi-honest garbling schemes while incurring a small multiplicative overhead in efficiency. This can benefit teams such as [TLSNotary](https://github.com/tlsnotary/tlsn) and [Cursive](https://www.cursive.team/) and in general pave the path for convenient deployment of MPC applications. We will also provide a way to use authenticated garbling directly via web apps by using wasm bindings. ### Project Details * **Technology stack**: This project will build on MPZ's existing support for garbled circuits and add a protocol that achieves full malicious security, as opposed to asymmetric privacy provided by the current DEAP protocol. * **Core protocols:** We will add authenticated garbling as another protocol alongside DEAP in mpz-garble and provide benchmarks as well as a testing suite. * **Relevant prior work:** Our implementations will closely follow the existing C++ implementations for authenticated garbling in [EMP Toolkit](https://github.com/emp-toolkit/emp-agmpc).We will ensure consistency with the existing MPZ codebase while translating this implementations. ## Team ### Team members * Names of team members: Nakul Khambhati * Email: nakulkhambhati@g.ucla.edu * Telegram handle: @nakstar123 * Discord handle: nakul2105 * Notion Account (If different from the above email) ### Team Website * N/A ### Team's experience Please describe the team's relevant experience. Some links would be useful. *Personal experience:* Nakul is starting his PhD at UCLA in January, 2025. He has been doing research in applied MPC for 1.5 years and spent most of his time working on two projects. The first involves using mixed circuit MPC to verify a set of certificates provided by two parties and output the intersection of the verified certifiers. The other enables shared access to an encrypted web client that allows joint authenticate to a server using secret shared credentials. The core technology required in this work is TLS-in-MPC, similar to what TLSN uses. Both works achieve malicious security in the dishonest majority setting so he has experience working with authenticated garbling, in particular the [WRK17a](https://eprint.iacr.org/2017/030) construction, including making white box modifications to it for security across sequential iterations, mixed circuits, etc. ### Team Code Repos * https://github.com/<your_repo_1> ## Development Roadmap: ### Overview * **Total Estimated Duration:** 4 months * **Full-time equivalent (FTE):** 2 * **Total Costs:** $18,000 ### Milestone 1: Auth garbling in trusted dealer model * **Estimated Duration:** 1 month * **FTE:** 0.5 * **Costs:** $4,500 * **Estimated delivery date**: Jan 14, 2025 #### Deliverables and Specifications ##### 0a. Documentation We will provide both inline documentation of the code and a basic tutorial that explains the interface for using garbled circuits with malicious security, keeping the API consistent with the current semi-honest version in MPZ. We will also provide a way to benchmark the online phase of the protocol. We will defer benchmarking the preprocessing phase to the next milestone ##### 0b. Testing Guide The code will have proper unit test and integration test coverage to ensure functionality and robustness. In the guide we will describe how to run these tests. ##### 1. Functionality: Function-dependent preprocessing We will write a piece of code that, assuming an ideal preprocessing functionality that provides authenticated AND triples, will be run by all parties to compute shares of the authenticated garbled circuit. This involves creating appropriate wire labels and MACs for each gate in the circuit and constructing tables using random permutation bits obtained in the preprocessing. All parties will broadcast their shares of the garbled circuit to an evaluator. This corresponds to Figure 4.1 on page 65 [here](https://www.cs.umd.edu/~jkatz/THESES/xiao.pdf). ##### 2. Functionality: Input processing and online phase We will write a piece of code that will process parties' inputs and share appropriate input labels for circuit evaluation. The evaluator will reconstruct the garbled circuit using the shares it has received, check for authenticity of shares and then evaluate the circuit in topological order. We will parallelize this so that the evaluation time is linear in the number of AND gates in the circuit. Finally, all parties send shares of output labels to the evaluator who broadcasts the final output of the circuit. This corresponds to Figure 4.2 on page 66 [here](https://www.cs.umd.edu/~jkatz/THESES/xiao.pdf). ##### 3. Functionality: Ideal preprocessing We will write a *temporary insecure* piece of code that generates the preprocessing material required for Functionality 1 and Functionality 2 to be tested. These will render the protocol insecure but will be replaced with secure instantiations in the next milestone. ##### 4. Application The secure implementation of the online phase will make calls to the insecure ideal functionality to provide a framework which can be tested. The deliverable will be a partially secure protocol for authenticated garbling which will have a similar interface to mpz-garble in the MPZ framework. Examples, benchmarks and a testing suite will also be included. ### Milestone 2: Auth garbling preprocessing and communication optimized protocol. * **Estimated Duration:** 1 month * **FTE:** 0.5 * **Costs:** $4,500 * **Estimated delivery date**: Feb 14, 2025 #### Deliverables and Specifications ##### 0a. Documentation We will provide both inline documentation of the code and a basic tutorial that explains the interface for using garbled circuits with malicious security, keeping the API consistent with the current semi-honest version in MPZ. We will also provide a way to benchmark the preprocessing phase of the protocol. ##### 0b. Testing Guide The code will have proper unit test and integration test coverage to ensure functionality and robustness. In the guide we will describe how to run these tests. ##### 1. Functionality: Authenticated bits and shares We will write a piece of code that allows parties to securely generate shares of authenticated bits and uses a consistency check to catch malicious behavior. These protocols will make calls to OT protocols that have already been implemented in mpz-ot crate of MPZ. These correspond to Figures 4.4 and 4.6 on page 76 and 77 [here](https://www.cs.umd.edu/~jkatz/THESES/xiao.pdf). ##### 2. Functionality: Authenticated AND triples We will write a piece of code that makes calls to the protocols for authenticated bit shares and generates authenticated AND triples. This corresponds to Figure 4.12 on page 85 [here](https://www.cs.umd.edu/~jkatz/THESES/xiao.pdf). ##### 3. Functionality: Optimized communication with half-gates We will upgrade the protocol from the previous milestone to one with roughly half the communication overhead. This will be based on the protocol from [here](https://eprint.iacr.org/2018/578) which has state of the art online communication in authenticated garbling. As an added benefit, this optimized protocol decouples privacy and authentication which makes it conceptually easier to understand the protocol. ##### 4. Application The insecure protocol from the previous milestone will be modified and optimized to make calls to the secure preprocessing protocols. The deliverable will be a secure protocol for optimized authenticated garbling which will have a similar interface to mpz-garble-core in the MPZ framework. Integrating this protocol into the MPZ virtual machine will be done in a future milestone. Examples, benchmarks and a testing suite will also be included. ### Milestone 3: Auth garbling with IO implemented in MPZ virtual machine * **Estimated Duration:** 1 month * **FTE:** 0.5 * **Costs:** $4,500 * **Estimated delivery date**: March 14, 2025 #### Deliverables and Specifications ##### 0a. Documentation We will provide both inline documentation of the code and a basic tutorial that explains the interface for using garbled circuits with malicious security, keeping the API consistent with the current semi-honest version in MPZ. We will also provide a way to benchmark the preprocessing phase of the protocol. ##### 0b. Testing Guide The code will have proper unit test and integration test coverage to ensure functionality and robustness. In the guide we will describe how to run these tests. ##### 1. Functionality: Memory store, View and Flush We will write a piece of code that implements a memory store, view interface and IO flushing commands, required to integrate the authenticated garbling protocol in the MPZ virtual machine. Implementing these traits provides a level of abstraction such that a user calling these functions need not worry about low level implementation details. ##### 2. Functionality: Functional 2 party authenticated garbling interface We will write a piece of code that integrates the core authenticated garbling protocol with the traits implemented for compatability with the MPZ virtual machine discussed above. The result will be a 2 party protocol, templated on a type of channel used for IO and a COT protocol for distributing initial correlated randomness. ##### 3. Application The deliverable will be a fully secure protocol for authenticated garbling which will have a similar interface to mpz-garble in the MPZ framework. Examples, benchmarks and a testing suite will also be included. ##### 4. Blog A blogpost will be published explaining the high-level ideas used in authenticated garbling, an informal argument about its security against malicious adversaries and a walkthrough of the codebase along with helpful comments for using authenticated garbling in applications. ### Milestone 4: Use cases of auth garbling * **Estimated Duration:** 1 month * **FTE:** 0.5 * **Costs:** $4,500 * **Estimated delivery date**: April 14, 2025 #### Deliverables and Specifications ##### 1. Application to Cursive's Trinity We will work in collaboration with Cursive to upgrade their Trinity protocol from semi-honest to malicious security using the MPZ authenticated garbling implementation. We will also research modifications that can be made in a server-aided security model where a semi-honest server distributes input-independent authenticated preprocessing material between the parties that wish to compute a function. This will enable non-interactive secure computation with malicious security, low online communication and optional input verification. ##### 2. Web assembly build for MPC framework We will work in collaboration with Andrew Morris from PSE to create a wasm build of authenticated garbling for use in web applications via [MPC framework](https://github.com/voltrevo/mpc-framework). We will build on [emp-wasm](https://github.com/voltrevo/emp-wasm) to integrate it directly with the Rust implementation in MPZ, add functionality for multithreading and use SIMD optimizations. We will provide a guide for using it and deploy a proof of concept web application. ##### 3. Blog A blogpost will be published explaining the pros and cons of authenticated garbling in different use cases, comparing its efficiency with FHE and secret-sharing based MPC protocols. We will motivate the need for malicious security by presenting attacks on current semi-honest implementations and argue that the overhead imposed by authenticated garbling in many settings is quite reasonable. Finally, we will describe security tradeoffs that would enable non-interactive secure computation by outsourcing expensive preprocessing to a semi-trusted server. ### Additional Information Vivek Bhupatiraju from [Cursive](https://www.cursive.team/) has expressed interest in using authenticated garbling for their applications. Andrew Morris from PSE is working on creating wasm bindings for the existing C++ implementation of authenticated garbling and has expressed an interest in substituting it with a Rust implementation in MPZ.