Proposal: Combining ZKP with FHE to replace bootstrapping

[000wan]

trafficstars

General Grant Proposal

• Project: https://github.com/privacy-scaling-explorations/acceleration-program/issues/18

Project Overview :page_facing_up:

Overview

This is a project combining ZKP with FHE to replace bootstrapping.

Project Details

The project aims to replace a bootstrapping process in Fully Homomorphic Encryption (FHE) with ZK proof. We aim to write a ZK circuit about the correctness of decryption and re-encryption on the client (trusted site) and integrate it with existing (or newly generated) FHE code. We will make a working program that appears whole FHE processes, specifically the ZK process, replaced from bootstrapping. We will design several test cases for verification of the program. Also, we will write multiple articles about the entire FHE process and our project, and make a final paper explaining our project.

• Language: Rust, C++, Python, Circom
• Theoretical Knowledge: FHE, ZKP

Team :busts_in_silhouette:

Team members

• Names of team members: YoungWan Kwon (@000wan)
• Email (Required): [email protected]
• Telegram handle: phenol0
• Discord handle: 000wan

• Names of team members: Changmin Cho (@indextree)
• Email (Required): [email protected]
• Telegram handle: indextree
• Discord handle: index.tree

Team Website

• https://zk-strapping.github.io/

Team's experience

• Finished 2023 ZK Summer Contribution Program
• 2nd place on Ethcon Korea 2023: torch2circom, Built upon keras2circom and circomlib. Implemented some mathematical libraries about matrix operations.

Team Code Repos

• https://github.com/ZK-Strapping/ZK-Strapping

Development Roadmap :nut_and_bolt:

Overview

• Total Estimated Duration: 8 weeks
• Full-time equivalent (FTE): 1.0
• Expected Start Date: Jan 15th 2024
• Expected End Date: Mar 10th 2024

Milestone 1: Implementing FFT in ZKP (grant will only be given them for milestone1 for now)

• Estimated Duration: 4 weeks
• FTE: 1.0
• Estimated delivery date: Feb 11st 2024

Since FFT is essential for CKKS scheme, this milestone aims to provide at least working (even if inefficient) real number FFT circuit in ZK. We’ll try to use zkVM or zkLLVM tools for this.

1. We will first learn about zkLLVM or zkVM tools like Nil or RISC0. (For ~1 week)
   • https://docs.nil.foundation/nil/
   • https://dev.risczero.com/api/
2. We will design real-number FFT proof using RISC0, Nil. We’re planning to meet offline and write codes concentratedly. The work process will be shared via Telegram group.
3. Furthermore, we will learn the details and implementations of CKKS scheme. We will write an article about CKKS and upload to our Github blog. (For ~3 week)

Milestone 2 (grant will only be given them for milestone1 for now)

• Estimated Duration: 3 weeks
• FTE: 1.0
• Estimated delivery date: Mar 3rd 2024

We will implement CKKS scheme in ZK circuit if Milestone 1 succesfully ends.

It will include writing zk circuits, designing proper tests, and writing a documentation post in GitHub.

The details will be decided after completion of the Milestone 1.

Milestone 3 (grant will only be given them for milestone1 for now)

• Estimated Duration: 1 week
• FTE: 1.0
• Estimated delivery date: Mar 10th 2024

We will make the final article(paper) about what we’ve done, and upload it on GitHub page.

Additional Information :heavy_plus_sign:

Milestone 1 repo: https://github.com/ZK-Strapping/zk-fft Team blog repo: https://github.com/ZK-Strapping/ZK-Strapping.github.io

It's agreed by FHE research team and applicants that the grant will only be given them for milestone1. If the milestone 1 accomplished well the following milestone could be consider to grant.