Master’s Thesis Presentation • Cryptography, Security, and Privacy (CrySP) • Private Two-Party Random Minimum Spanning Forest ComputationExport this event to calendar

Tuesday, August 23, 2022 — 9:00 AM to 10:00 AM EDT

Please note: This master’s thesis presentation will take place online.

Marian Dietz, Master’s candidate
David R. Cheriton School of Computer Science

Supervisor: Professor Florian Kerschbaum

Finding the Minimum Spanning Tree, or more generally the Minimum Spanning Forest (MSF), of a weighted graph is a well-known algorithmic problem. While this problem itself can be directly applied to any kind of networks, it also has less obvious applications like the approximation of the Traveling Salesman Problem. However, there is only limited work on efficiently computing an MSF in a two-party computation setting, where the input graph is split between two parties, and the goal is to find the MSF on the combined graph without leaking any information about the parties’ respective inputs.
Any prior work on this problem either follows a generic approach that builds a circuit in order to run it through general multi-party computation protocol, or requires a high number of communication rounds (usually at least linear in the graph size). In addition, all of these approaches assume that the edge weights are unique.

In this work, we are going to address these issues by first defining a lightweight and simple protocol with a low worst-case number of communication rounds, under the constraint that no two edges share the same weight. We then analyze the problems occurring after enabling the possibility of duplicated weights and look at the more general problem of generating a Random Minimum Spanning Forest, which defines a distribution of the desired output in case the MSF is not unique. We carefully design a protocol for the semi-honest security model in such a way that as many values as possible can be published in the early stages. This reveals information about the graph structure that is then used to reduce the number of communication rounds. By doing this we get a protocol that performs especially well whenever the number of identical weights is low, while it stays secure and correct regardless of the graph structure and its edge weights.


To join this master’s thesis presentation on Zoom, please go to https://uwaterloo.zoom.us/j/99562891462.

Location 
Online master’s thesis presentation
200 University Avenue West

Waterloo, ON N2L 3G1
Canada
Event tags 

S M T W T F S
25
26
27
28
29
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
1
2
3
4
5
6
  1. 2024 (80)
    1. April (8)
    2. March (22)
    3. February (25)
    4. January (25)
  2. 2023 (296)
    1. December (20)
    2. November (28)
    3. October (15)
    4. September (25)
    5. August (30)
    6. July (30)
    7. June (22)
    8. May (23)
    9. April (32)
    10. March (31)
    11. February (18)
    12. January (22)
  3. 2022 (245)
  4. 2021 (210)
  5. 2020 (217)
  6. 2019 (255)
  7. 2018 (217)
  8. 2017 (36)
  9. 2016 (21)
  10. 2015 (36)
  11. 2014 (33)
  12. 2013 (23)
  13. 2012 (4)
  14. 2011 (1)
  15. 2010 (1)
  16. 2009 (1)
  17. 2008 (1)