search

Crypto-TII / mpc_graph_theory_lib

SCALE-MAMBA implementation of basic graph theory functionality
MIT License
2 stars 1 forks source link

Missing file test_graph.mpc #1

Open gutjuri opened 12 months ago

gutjuri commented 12 months ago

Hello :) I have read your paper and wanted to try out your implementation of Dijkstra's algorithm. The README mentions a test_graph.mpc file, however, it seems to be missing in this repository. Could you please point me into a direction on where to find this file if you have released it? I'd be glad to hear from you! Best regards, Juri

abdelrahamanaly commented 12 months ago

Hi Juri! Thanks for the interest. You can try it out! Indeed now that I check is missing. Let me check and come back to you. In the meantime you can use it by invoking the main dijkstra function with a new he adjacency matrix as input and the source vertex

gutjuri commented 12 months ago

On my fork of your project, I ported the algorithm to run on MP-SPDZ, as I was unable to get SCALE-MAMBA to run. See this file: https://github.com/gutjuri/mpc_graph_theory_lib/blob/main/mpc_graph.py

I have run an experiment using the following graph:

flowchart LR
    0 -- 1 --- 1
    0 -- 3 --- 2
    1 -- 1 --- 3
    2 -- 1 --- 3
    2 -- 4 --- 4
    3 -- 50 --- 4

When picking vertex 0 as the source, the algorithm runs in about 426ms (using MP-SPDZ's semi-party (semi-honest with dishonest majority, see https://mp-spdz.readthedocs.io/en/latest/readme.html?highlight=shamir#secret-sharing) and two parties). This is worse than in your paper. I still need to investigate why this is the case.

Could you share the graphs that you used when performing benchmarks? I would love to use those to optimise my MP-SPDZ implementation in order to reach the performance of your algorithm.

Also, I would like to ask you how you conducted the experiments as a 3-party computation as described in your paper? From my understanding, one computation party holds the (secret) source vertex label, and the other party holds the (secret) graph weights. Is this correct? What is the role of the third party?

Best, Juri

abdelrahamanaly commented 11 months ago

Hi Juri!

Sorry it took so long, but I was busy with conferences and some personal issues. I have updated the library and introduce test cases showing how it works. Note that we still assume some permutation happens at some point. Im looking for a nice Walksman implementation to add that as well. I also include some of the graphs we tested.

Note also that performance greatly depends on setup. Take into account communications (ping time) or capabilities of the server. We used quite powerful machines for the benchmarking.

An additional note is that the paper reports online only timings. So when benchmarking you have to separate online from offline.

On the setup, well who knows what, is defined by the use case, for experimentation purposes you only really care that data is secret shared with the ideal functionality, and then you ask the question, what is the shortest path given this matrix.

If you have further questions let me know.