 |
 |
 |
|---|---|---|
 |
 |
 |
 |
 |
 |
- Multi-Party Computation Cryptography - Final Project
- Files & Project structure
Table of contents generated with markdown-toc
This project is an implementation of a secure multi-party protocol for the secure set-union problem and the secure all-pairs shortest distance problem. The protocol is devised from existing literature and is tailored for enhanced efficiency in a semi-honest setting with a dishonest majority.
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.
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 distance 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.
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 Distance functionality from Justin Brickell and Vitaly Shmatikov resarch to contribute to the ecosystem of implementations, aiming to create more efficient implementations in this domain.
There were two algorithms for the set union to implement in our protocol:
- 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.
- A tree pruning method that utilized ElGamal and BitOr to reveal information securely.
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.
Implement a Set-Union mechanism between two private groups of numbers.
For sharing the necessary information between two parties, we Use ElGamal Encryption BitOr Mechanism.
sequenceDiagram
actor Alice
actor Bob
par send request
ServerA ->> Alice : 1 or 0
activate Alice
ServerB ->> Bob : 1 or 0
end
Alice ->> Alice: k
Alice ->> Bob: Ca , q , g , g^k
deactivate Alice
activate Bob
Bob ->> Alice : Cb
deactivate Bob
activate Alice
par Return the same result
Alice ->> ServerA : Algo result is 1 or 0
Alice ->> Bob: Algo result
Bob ->> ServerB : Algo result
end
deactivate Alice
Procedure PrivacyPreservingBitOr:
- 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)})$
- Selects cyclic group
- Alice sends
$(C_a, q, g, g^k)$ to Bob, keeping k private - 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')
- Picks random
- Bob sends
$C_b$ back to Alice - Alice receives
$C_b$ , unpacks it into$(γ, δ)$ - Calculates
$b = \frac{δ}{γ^k}$ - If
$b = 1$ , returns$0$ - If
$b ≠ 1$ , returns$1$
- If
- Calculates
Each graph has a public graph, and a personal graph (its original graph), and with the help of the algorithm we used.
each side updates the edges in the public graph, until the distances are updated to be the shortest in both.
Utilizes the Set Union Protocol and Enhances the capabilities into a secure computation of the All Pairs Shortest Distance between nodes in a graph.
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.
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
POST /apsp
| Parameter | Type | Description |
| :-------- | :------- | :------------------------- |
| graph | nx graph like json | Required. JSON of Graph |
POST /union
| Parameter | Type | Description |
| :-------- | :------- | :-------------------------------- |
| list | list [ int ] | Required. list of numbers |
Client: HTML CSS JAVASCRIPT
Server: PYTHON http module
result = unionA(json_data["content"], 32, server_socket=server_socket) result = unionB(json_data["content"], 32) ## 16 result = ASPS1(graph, server_socket_dont_touch=server_socket) result = ASPS2(graph)Insert gif and image for the video demo on youtube
Clone the project
git clone [https://link-to-project](https://github.com/Cryptography-mpc/Final-Project-Multiple-Party-Computation-Cryptograpy.git)
Go to the project directory
cd Final-Project-Multiple-Party-Computation-Cryptograpy
Install dependencies
pip install sympy numpy networkx
Start the for alice
python3 serv1.py
Start the for bob
python3 serv2.py
by Justin Brickell and Vitaly Shmatikov The University of Texas at Austin, Austin TX 78712, USA
by Yehuda Lindell∗ Benny Pinkas June 26, 2006
for original code go here
- 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