Proposal: PIR for hash path retrieval

[iammadab]

General Grant Proposal

• Project: https://github.com/privacy-scaling-explorations/acceleration-program/issues/14 PIR for Hash Path Retrieval

Project Overview :page_facing_up:

Overview

Merkle hash path retrieval using PIR.

Project Details

In most cases, when the hash path is sensitive, applications have to maintain the tree (or have a way to recompute the tree) to compute the hash path privately.

This project aims to mitigate this by using PIR to privately request the hash path for some encrypted index query.

Output:

• Rust library for authenticated data structure operations + private hash path retrieval.
• Document describing design decisions and implementation.

Team :busts_in_silhouette:

Team member

• Names of team members: Wisdom Ogwu
• Email: [email protected]
• Telegram handle: wmadab
• Discord handle: iammadab

Team member

• Names of team members: Ginika Chinonso
• Email: [email protected]
• Telegram handle: NonsoFrancis
• Discord handle: mikefrancis

Team's experience

We have experience with ZK, FHE, and building complex systems.

ZK:

• https://github.com/iammadab/zk
• https://github.com/Ginika-Chinonso/crypto_primitives.git

Merkle AVL Tree:

• https://github.com/dashpay/grovedb/blob/master/adr/merk-proofs.md
• https://github.com/dashpay/grovedb

Team Code Repos

• https://github.com/builldx/merkle-pir

Development Roadmap :nut_and_bolt:

Overview

• Total Estimated Duration: 4 weeks
• Total Estimated Working Hours: 120 hrs
• Expected Start Date: March 4th, 2024
• Expected End Date: April 1st, 2024

Milestone 1: Design Document detailing mechanism for private hash path retrieval

• Estimated Duration: 2 weeks
• FTE: 0.75
• Estimated delivery date: March 18th, 2024

Here we explore the solution space, settle on concrete decisions and write a document detailing our decision and why we made them. Some interesting things to explore:

• best representation for the authenticated data structure / are there some authenticated data structures that this won’t work with?
• private construction of full query from the user’s private seed query
  • e.g. user specifies index on the leaf layer and the index for all other layers are privately constructed.

Milestone 2: Rust library implementation

• Estimated Duration: 2 weeks
• FTE: 0.75
• Estimated delivery date: April 1st, 2024

1. Pick a specific authenticated data structure, implement its operations
2. Implement method for privately retrieving its authentication information (e.g. hash path).
   • ability to encrypt query
   • ability to produce encrypted hash path proof
   • ability to decrypt encrypted hash path proof
   • tfhe-rs or sunscreen will be used to implement the fhe logic
3. Add use-case documentation to library readme

[NOOMA-42]

Would you be able to elaborate more on the following question?

1. What scheme do they plan to use and why ? For ex, I think the most practical schemes are Y-PIR or hintelessPIR
2. Neither tfhe-rs nor Sunscreen can be used to construct practical PIR schemes. Any reasoning on why did they choose tfhe-rs/sunscreen?

[iammadab]

We intend to use the YPIR scheme because in most cases, the database will be dynamic and YPIR doesn't require offline communication and has great throughput tradeoffs. We also intend to explore other schemes during the milestone 1 phase with a focus on minimizing server cost.

[NOOMA-42]

@Janmajayamall kindly let us know what else feedback you have :)