-
Notifications
You must be signed in to change notification settings - Fork 1
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Missing file test_graph.mpc #1
Comments
Hi Juri! |
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). 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 |
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. |
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
The text was updated successfully, but these errors were encountered: