addy-mpc 0.0.1

mpc implementation of all pairs shortest path

Multi-Party Computation Cryptography - Final Project

• finish writing the development process api and demo and screenshots adding tests
• fix the SSD document https://docs.google.com/document/d/1oWhDiyfaaCHef23QWVzcB4Yah-8EvjGF3wODgSoSex4/edit#

• Multi-Party Computation Cryptography - Final Project
  • About
  • What is Multi-Party Computation (MPC)?
  • Authors
  • Project Overview
    • Project Goal
    • Introduction
    • Methods & Algorithms
      • Design Considerations
      • Selected approach
    • Pseudo Code Bit OR
      • Procedure PrivacyPreservingBitOr:
      • Infrastracture
        • User Interface
  • Development proccess
  • API Reference
    • Get item
    • add(num1, num2)
  • Appendix
  • License
  • Tech Stack
  • Usage/Examples
  • Demo
  • Environment Variables
  • Run Locally
• Files & Project structure

Table of contents generated with markdown-toc

About

This project is an implementation of a secure multi-party protocol for the secure set-union problem and the secure all-pairs shortest path problem. The protocol is devised from existing literature and is tailored for enhanced efficiency in a semi-honest setting with a dishonest majority.

What is Multi-Party Computation (MPC)?

Multi-Party Computation (MPC) is a subfield of cryptography that enables multiple entities to jointly compute a function over their inputs while keeping those inputs private. In the context of this project, we focus on a 2-party computation, where both entities share inputs and follow the MPC protocol, ensuring the privacy of their inputs. Without the intervention of a server (Third party) in the proccess.

Authors

• @Dolev Dublon
• @Yakov Khodorkovski
• @Daniel Zaken
• @Aviad Gilboa

Project Overview

Project Goal

The primary objective of this project is to implement a secure multi-party protocol that is specifically designed for the secure set-union problem and the secure all-pairs shortest path problem. Our protocol aims to achieve greater efficiency than generic MPC protocols, especially in semi-honest settings with a dishonest majority. We base our approach on existing research by Justin Brickell and Vitaly Shmatikov, which you can access here.

Introduction

Our protocol deals with two semi-honest groups. Since the late 1980s, general protocols have theoretically allowed secure computation in polynomial time and with a security parameter, enabling both players to compute safely under computational complexity assumptions. While these general protocols are theoretically efficient, they are not always practically efficient. Therefore, people have been trying to create specific security protocols for specific functions that are more efficient than the general protocols.

The use of various generic libraries, such as YAO, and GMW, has proven to be less efficient, prompting efforts to develop more efficient approaches. We will implement the All-Pairs Shortest Path functionality to contribute to the ecosystem of implementations, aiming to create more efficient implementations in this domain.

Methods & Algorithms

Design Considerations

There were two algorithms for the set union to implement in our protocol:

1. A provided pseudocode that utilized YAO and GMW for the calculation of the minimum using a generic library. However, this did not fit with our chosen programming language.
2. A tree pruning method that utilized ElGamal and BitOr to reveal information securely.

Selected approach

We have decided to implement the BitOr operation to achieve a union without relying on a generic library.

Image	Cryptographer	Link
	Elgamal	Wikipedia
	Yao	Wikipedia

because the iterative method required using a generic library to calculate the minimum in a secure way.

Pseudo Code Bit OR

Procedure PrivacyPreservingBitOr:

1. Alice initializes:
   • Selects cyclic group $G$ of prime order $q$
   • Chooses $g$ (quadratic residue) and large prime p $(p=2q+1)$
   • Chooses private key $k ∈ {0, ..., q-1}$
   • Picks random $r ∈ {2, ..., q-1}$
   • If Alice's bit is $0$, calculates $C_a = (g^r, g^{(kr)})$
   • If Alice's bit is $1$, calculates $C_a = (g^r, g\cdot g^{(kr)})$
2. Alice sends $(C_a, q, g, g^k)$ to Bob, keeping k private
3. Bob receives $(C_a, q, g, g^k)$ and unpacks $C_a$ into $(α, β)$
   • Picks random $r' ∈ {2, ..., q-1}$
   • If Bob's bit is $0$, calculate C_b = (α^r', β^r')
   • If Bob's bit is $1$, calculate C_b = (α^r', g^r'*β^r')
4. Bob sends $C_b$ back to Alice
5. Alice receives $C_b$, unpacks it into $(γ, δ)$
   • Calculates $b = \frac{δ}{γ^k}$
     • If $b = 1$, returns $0$
     • If $b ≠ 1$, returns $1$ insert diagram here

Infrastracture

Using Flask and Gunicorn servers on cloud platforms of Microsoft Azure. we represent parties involved in the secure computation.

User Interface

We built a library mainly for software developers, but included visual aids and infrastructure for easier understanding. It's designed to show anyone how our system works, especially in Multi-party computation. Our simple interface gives a clear view of the protocol's progress and even includes a log output to follow the entire process.

Insert screens here

[ QR code for GitHub repo on bottom-right ]

Development proccess

At first the Development process was to read a lot and get deep into the article of Justin Brickell and Vitaly Shmatikov, which you can access here. and we met every week from the begining reading it, and also reading the article A Proof of Security of Yao’s Protocol for Two-Party Computation by Yehuda Lindell Benny Pinkas and we had to learn a lot about the secure computation proofs and theory Semi-Honest Adversaries and this lecture as well. This is the first step is to get into the field so we can understand the problem more deeply. then we wrote the

Synchronization was one of our biggest obstacle for us as a team and for the threads in the program between the clients

API Reference

GET /api/datapoint

| Parameter | Type | Description |

| :-------- | :------- | :------------------------- |

| api_key | string | Required. Your API key |

Get item

GET /api/items/${id}

| Parameter | Type | Description |

| :-------- | :------- | :-------------------------------- |

| id | string | Required. Id of item to fetch |

add(num1, num2)

Takes two numbers and returns the sum.

Appendix

Any additional information goes here

License

MIT

Tech Stack

Client: HTML CSS JAVASCRIPT, Jinja engine for flask Server: PYTHON FLASK

Usage/Examples

import  Component  from  'my-project'

  

function  App()  {

return  <Component />

}

Demo

Insert gif and image for the video demo on youtube

Deployment

1. get a user on Microsoft Azure

To deploy this project run

gunicorn 

Environment Variables

To run this project, you will need to add the following environment variables to your .env file

API_KEY

ANOTHER_API_KEY

Run Locally

Clone the project

git clone https://link-to-project

Go to the project directory

cd my-project

Install dependencies

pip install flask .....

Start the server

npm run start

Files & Project structure

Documents

Vision Statement - MPC protocol implementation

Vision Statement

SRD Document

Privacy-Preserving Graph Algorithms in the Semi-honest Model

by Justin Brickell and Bitaly Shmatikov The University of Texas at Austin, Austin TX 78712, USA

A Proof of Security of Yao’s Protocol for Two-Party Computation

by Yehuda Lindell∗ Benny Pinkas June 26, 2006

for original code go here

• https://github.com/Dolev-Dublon/Final-Project-Multiple-Party-Computation-Cryptograpy

notes

• notes for final project https://docs.google.com/document/d/1d35ExjbP7p1KzuKcKIswkkOI2wedrJmxIr1OTyWHQyg/edit#
• vistion statements notes https://docs.google.com/document/d/1xL3wtaWKGzi0FGTweE9COot-9TdP_mHv4BdzA2mkEAg/edit?usp=sharing
• SSD https://docs.google.com/document/d/1oWhDiyfaaCHef23QWVzcB4Yah-8EvjGF3wODgSoSex4/edit?usp=sharing
• SRD https://docs.google.com/document/d/1w5ZWddqB6iOTN4Ku2wOdZLmmxYpQKhgURkkDfFiViZY/edit?usp=sharing