# General Grant Proposal * **Project:** PADO ## Project Overview :page_facing_up: ### Overview Interactive Zero-Knowledge (IZK) proofs are another type of zero-knowledge proof system, in which the proof consists of a multi-round protocol between the prover and verifier. IZK is quite scalable for large statements, it also enjoys cheap computation and memory costs without any trusted setup. We believe it will become a key building block for Web3 applications, where privacy is a main concern. This project is the first step to build an open-source Rust implementation of state-of-the-art IZK protocols. This project aims to implement the silent OT extension protocol [Ferret](https://eprint.iacr.org/2020/924). ### Project Details This project aims to implement and optimize the silent OT extension protocol [Ferret](https://eprint.iacr.org/2020/924) in Rust. Oblivious Transfer (OT) protocol is an essential tool in cryptography that provides a wide range of applications in secure multi-party computation. The OT protocol has different variants such as 1-out-of-2, 1-out-of-n, and k-out-of-n. Here we only focus on 1-out-of-2. An OT protocol involves two parties: the sender and the receiver. The sender has 2 strings, whereas the receiver has a chosen bit. After the execution of this OT protocol, the receiver obtains one of the strings according to the chosen bit, but no information of the other string. Then sender gets no information about the chosen bit. A Correlated OT (COT) is a special type of OT in that the strings of the sender are correlated by a global secret $\Delta$. Due to a result of Impagliazzo and Rudich in this [paper](https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.14.6170&rep=rep1&type=pdf), it is very unlikely that OT is possible without the use of public-key cryptography. However, OT can be efficiently extended. Starting with a small number of base OTs, one could create many more OTs with only symmetric primitives. The seminal work of [IKNP03](https://www.iacr.org/archive/crypto2003/27290145/27290145.pdf) presented a very efficient protocol for extending OTs, requiring only black-box use of symmetric primitives and a small number (say, 128) of base OTs. Silent OT extension is a new type of OT extension that significantly reduces the communication cost of IKNP-type OT extensions. It involves new design principles with different building blocks, which are the main contents that this project aims to implement. The expected final state includes the following: * A comprehensive specification of the current implementation of the Ferret protocol. It contains all the protocol details and optimizations. This specification follows the Ferret [paper](https://eprint.iacr.org/2020/924), but in an easy-to-understand way for developers. * A detailed inline API documentation that guides developers using the library. Easy-to-use test and bench suites are provided as well. * Basic building blocks that will be used in all the protocols * Network IO is used to send and receive messages, it is essentially a wrap of the tokio repo. * 128-bit block data type and all the required operations on it. Particularly, the operations include the multiplication over Galois Field ($\small \mathbb{F}_{2^{128}}$). * Pseudo-Random Generator (PRG), Pseudo-Random Permutation (PRP), and hash functions based on AES. * The Goldreich-Goldwasser-Micali tree (GGM tree) and its optimizations based on PRG. * Learning Parity with Noise (LPN) encoding and optimizations. The LPN encoding algorithm includes two types. The first type is LPN with a regular noise distribution, and the other type is LPN with uniform noise. * Sub-protocols * Single-Point COT (SPCOT) with semi-honest and malicious security. * Multi-Point COT (MPCOT) with semi-honest and malicious security. * Iterative Correlated OT Extension, i.e., the complete Ferret protocol. ## Team :busts_in_silhouette: ### Team members * Project leader * Name: Xiang Xie * Email: xiang@padolabs.org * Telegram handle: xiang_xie * Github: https://github.com/xiangxiecrypto * Google Scholar: https://scholar.google.com/citations?user=WWb0js4AAAAJ&hl=zh-CN * Engineers: * Name: Yilin Yan * Email: yanyilin@padolabs.org * Github: https://github.com/ujnss * Name: Jiqing Xiao * Email: xiaojiqing@padolabs.org ### Team Website * https://www.padolabs.org ### Team's experience Members of the team have rich experience including cryptography protocol design and cryptographic engineering. Some previous works are listed as the following. - **Rosetta:** an open-source framework for privacy-preserving machine learning with TensorFlow as the front-end, and compiled into various cryptographic protocols including MPC/ZK/HE. - [https://github.com/LatticeX-Foundation/Rosetta](https://github.com/LatticeX-Foundation/Rosetta) - **OpenTSS:** an open-source threshold signature scheme library for multi-party ECDSA schemes from class groups. - [https://github.com/LatticeX-Foundation/opentss](https://github.com/LatticeX-Foundation/opentss) - **Proof-of-Custody in MPC**: an open-source project for estimating the performance and feasibility of the MPC proof-of-custody mechanism. - [https://github.com/PlatONnetwork/proof_of_custody](https://github.com/PlatONnetwork/proof_of_custody) Papers about interactive zero-knowledge proofs published by our team members - AntMan (CCS’22): https://eprint.iacr.org/2022/566 - Mystique (USENIX Security' 21): https://eprint.iacr.org/2021/730 ### Team Code Repos * https://github.com/pado-labs ## Development Roadmap :nut_and_bolt: This section should break out the development roadmap into a number of milestones. Since the milestones will appear in the grant contract, it helps to describe the functionality we should expect, plus how we can check that such functionality exists. Below we provide an **example roadmap**. We recommend that the scope of the work can fit within a 3 month period and that teams structure their roadmap as 2 weeks = 1 milestone. For each milestone: * Please be sure to include a specification of the software. The level of detail must be enough so that we are able to verify that the software meets the specification. * Please include total amount of funding requested per milestone. * Please note that we require documentation (e.g. tutorials, API specifications, architecture details) in each milestone. This ensures that the code can be widely used by the community. * Please provide a test suite, comprising unit and integration tests, along with a guide on how to run these. * Please indicate the milestone duration, as well as number of Full-Time Employees working on each milestone, and include the number of days along with their cost per day. ### Overview * **Total Estimated Duration:** 26 weeks * **Full-time equivalent (FTE):** 0.6 (0.2+0.2+0.2) * **Total Costs:** $29120 * **Starting Date:** 19th June 2023 The cost of a senior cryptography researcher is $60 per hour, and the cost of a cryptography engineer is $40 per hour. The total costs is $(26\times5\times8\times0.2) \times (60+40\times2) = 29120$ ### Milestone 1 Network IO and 128-bit Block Data Type * **Estimated Duration:** 2 weeks * **FTE:** 0.6 (0.2+0.2+0.2) * **Costs:** $2240 * **Estimated delivery date**: 5th July 2023 (excluding 2 days off for the Dragon Boat Festival) #### Deliverables and Specifications ##### 0b. Documentation We will provide inline documentation and examples explaining how a developer uses these APIs. ##### 0c. Testing Guide The code will have proper unit-test coverage (e.g. 90%) to ensure functionality and robustness. In the guide we will describe how to run these tests. A bench suite is also provided to test the performance of important functions. ##### 1. Functionality: Abstraction of Network IO and Related Implementations. We will write a piece of code that enable developers to send and receive data via the network. This is essentially a simplified wrapper of tokio, that is suitable for this project. ##### 2. Functionality: Implement a 128-bit Block Data Type and Its Operations. We will write a piece of code that define and implement a 128-bit chunk type and related operations. An important operation is the multiplication of Galois Field ($\small \mathbb{F}_{2^{128}}$), which takes as input two 128-bit strings and outputs the multiplication (a 128-bit string) defined in $\small \mathbb{F}_{2^{128}}$. This is the most common data type used in this project. Will use the SSE instruction set whenever possible to speed up. ### Milestone 2 PRG and PRP and Hash Functions Based on AES * **Estimated Duration:** 2 weeks * **FTE:** 0.6 (0.2+0.2+0.2) * **Costs:** $2240 * **Estimated delivery date**: 19th July 2023 #### Deliverables and Specifications ##### 0b. Documentation We will provide inline documentation and examples explaining how a developer uses these APIs. ##### 0c. Testing Guide The code will have proper unit-test coverage (e.g. 90%) to ensure functionality and robustness. In the guide, we will describe how to run these tests. A bench suite is also provided to test the performance of important functions. ##### 1. Functionality: PRG and PRP Based on AES We will write a piece of code that will implement the functionalities of PRG and two-key PRP. * A PRG takes as input a random seed and generates a (pseudo)random string with arbitrary length. We will use AES-ECB as a PRG, and use AES-NI whenever possible to speed up. This functionality will be used to generate random strings in the protocol. * A two-key PRP (pseudo-random permutation) is instantiated with two random keys. It takes as input a 128-bit string and outputs a permutation. This functionality will be used to generate the GGM tree. ##### 2. Functionality: Hash Functions Based on AES We will write a piece of code that will implement the circular correlation robustness hash function (CCRH). We will use AES to implement this hash function and use AES-NI whenever possible to speed up. This functionality will be used in SPCOT and MPCOT. ### Milestone 3 GGM Tree Generation. * **Estimated Duration:** 2 weeks * **FTE:** 0.6 (0.2+0.2+0.2) * **Costs:** $2240 * **Estimated delivery date**: 2nd August 2023. #### Deliverables and Specifications ##### 0b. Documentation We will provide inline documentation and examples explaining how a developer uses these APIs. ##### 0c. Testing Guide The code will have proper unit-test coverage (e.g. 90%) to ensure functionality and robustness. In the guide, we will describe how to run these tests. A bench suite is also provided to test the performance of important functions. ##### 1. Functionality: GGM Tree Generation We will write a piece of code that will implement the GGM tree. A [GGM tree](https://crypto.stanford.edu/pbc/notes/crypto/ggm.html) is a well-known construction of PRF (pseudo-random function) from PRG. This functionality will be used in the SPCOT protocol. ### Milestone 4 LPN Encoding and Optimizations. * **Estimated Duration:** 3 weeks * **FTE:** 0.6 (0.2+0.2+0.2) * **Costs:** $3360 * **Estimated delivery date**: 23th August 2023 #### Deliverables and Specifications ##### 0b. Documentation We will provide inline documentation and examples explaining how a developer uses these APIs. ##### 0c. Testing Guide The code will have proper unit-test coverage (e.g. 90%) to ensure functionality and robustness. In the guide, we will describe how to run these tests. A bench suite is also provided to test the performance of important functions. ##### 1. Functionality: LPN Encoding and Optimizations We will write a piece of code that will implement the LPN encoding algorithms. LPN encoding takes as input a vector $\mathbf{s}\in \mathbb{F}^{k}_{\small 2^{128}}$, a matrix $\mathbf{A}\in\mathbb{F}_2^{k\times n}$ and a sparse vector $\mathbf{e}\in\mathbb{F}_2^n$ with Hamming weight $t$, compute $\mathbf{s}\cdot \mathbf{A}+\mathbf{e}\in\mathbb{F}^{n}_{\small 2^{128}}$ for very large $n$. Since $\mathbf{A}$ is a uniformly random matrix, we will use a PRG to generate it. ### Milestone 5 SPCOT. * **Estimated Duration:** 5 weeks * **FTE:** 0.6 (0.2+0.2+0.2) * **Costs:** $5600 * **Estimated delivery date**: 27th September 2023 #### Deliverables and Specifications ##### 0b. Documentation We will provide inline documentation and examples explaining how a developer uses these APIs. ##### 0c. Testing Guide The code will have proper unit-test coverage (e.g. 90%) to ensure functionality and robustness. In the guide, we will describe how to run these tests. A bench suite is also provided to test the performance of important functions. ##### 1. Functionality: SPCOT Subprotocol We will write a piece of code that will implement the SPCOT subprotocol. The SPCOT protocol involves two parties: a sender and a receiver. The sender takes as input a global random string $\small \Delta\in\mathbb{F}_{2^{128}}$, the receiver takes as input a $n$-bit string $\mathbf{u}$ with a signle non-zero bit. The SPCOT protocol outputs uniform $\mathbf{v}\in\mathbb{F}_{2^{128}}^n$ to the sender and uniform $\mathbf{w}\in\mathbb{F}_{2^{128}}^n$ to the receiver, such that $\mathbf{v} = \mathbf{w}\oplus\mathbf{u}\cdot\Delta$. This functionality will be used in the MPCOT protocol. ### Milestone 6 MPCOT. * **Estimated Duration:** 6 weeks * **FTE:** 0.6 (0.2+0.2+0.2) * **Costs:** $6720 * **Estimated delivery date**: 15th November 2023 (excluding 7 days off for National Day holiday) #### Deliverables and Specifications ##### 0b. Documentation We will provide inline documentation and examples explaining how a developer uses these APIs. ##### 0c. Testing Guide The code will have proper unit-test coverage (e.g. 90%) to ensure functionality and robustness. In the guide, we will describe how to run these tests. A bench suite is also provided to test the performance of important functions. ##### 1. Functionality: MPCOT Subprotocol We will write a piece of code that will implement the MPCOT subprotocol. The MPCOT protocol is an extension of SPCOT and will use SPCOT as a building block. The sender takes as input a global random string $\small \Delta\in\mathbb{F}_{2^{128}}$, the receiver takes as input a $n$-bit string $\mathbf{u}$ with $t$ non-zero bits. The MPCOT protocol outputs uniform $\mathbf{v}\in\mathbb{F}_{2^{128}}^n$ to the sender and uniform $\mathbf{w}\in\mathbb{F}_{2^{128}}^n$ to the receiver, such that $\mathbf{v} = \mathbf{w}\oplus\mathbf{u}\cdot\Delta$. This functionality will be used in the iterative COT extension protocol. ### Milestone 7 Iterative Correlated OT Extension and a Blogpost. * **Estimated Duration:** 6 weeks * **FTE:** 0.6 (0.2+0.2+0.2) * **Costs:** $6720 * **Estimated delivery date**: 27th December 2023 #### Deliverables and Specifications ##### 0b. Documentation We will provide inline documentation and examples explaining how a developer uses these APIs. ##### 0c. Testing Guide The code will have proper unit-test coverage (e.g. 90%) to ensure functionality and robustness. In the guide, we will describe how to run these tests. A bench suite is also provided to test the performance of important functions. ##### 1. Functionality: Iterative COT Extension (Ferret) We will write a piece of code that will implement the complete Ferret protocol via bootstrapped iterations. We first combine MPCOT and LPN encoding to generate COTs. In order to generate more COTs, part of the previously generated COTs will be used as the seed to extend. This will avoid the heavy setup phase and significantly improve efficiency. The sender takes as input a global random string $\small \Delta\in\mathbb{F}_{2^{128}}$. The Ferret protocol outputs uniform $\mathbf{v}\in\mathbb{F}_{2^{128}}^n$ to the sender, and uniform $\mathbf{w}\in\mathbb{F}_{2^{128}}^n$, $\mathbf{u}\in\mathbb{F}_2^n$ to the receiver, such that $\mathbf{v} = \mathbf{w}\oplus\mathbf{u}\cdot\Delta$. ##### 2. Functionality: A Blog Post about Ferret and Its Applications We will publish a blog post to explain the principle behind Ferret and introduce its potential applications in IZK. ## Additional Information :heavy_plus_sign: Any additional information that you think is relevant to this application that hasn't already been included. Possible additional information to include: * What work has been done so far?