Experimenting privacy: preserving single source shortest paths
Kadri Tõldsepp

Data networks involve routing processes to select paths along which traffic must be delivered. Usually metrics (costs) are associated to network edges to represent bandwidth, delays, hop counts, and communication costs. Since several paths are possible between two network nodes, the routing process is in charge of selecting the path that minimize the appropriate metric.
Privacy is a main barrier to enable metric-based routing among Internet Autonomous Systems, since they are competitive companies and unwilling to share their private information.

We have considered the single source shortest path problem, that represents the case in which all network nodes are interested to route packets to the same destination. Our first solution is based on a straightforward strategy: we implemented the Bellman-Ford algorithm in SecretC and deployed the resulting code on three  miners. The main drawback of this solution is centralization: the three miners are in charge of computing the routing information of all nodes. However, the implemented prototype allows us to benchmark more efficient approaches.

Our second solution addresses the centralization issue. It distributes the computation among a network of miners and actively involves the network nodes as computing agents. Currently we are investigating the benefits of relaxing the privacy constraints to speed-up the algorithms.