Keywords

1 Introduction

The (Single Source) Shortest Path problem (SPP), i.e. computing the shortest path between a source and all other vertices in a graph, is a commonly used subroutine in commercial applications. In many of these settings, data related to the computation of the problem such as elements of its configuration, graph topology or associated weights, can be considered private. Real life examples include telecommunication networks for banking or restricted topology combinatorial auctions, among others. In such environments, different parties could gain a competitive advantage by obtaining privately held information. Therefore, mechanisms to ensure secrecy, correctness and fairness are required.

In this work we introduce a Secure Multiparty Computation (MPC) data-oblivious protocol to securely solve the single source SPP. Just like in previous works, namely Aly et al. [2, 4], we propose a data oblivious version of Dijkstra’s algorithm, compatible with MPC. We consider all information related to the graph (aside from the number of vertices) to be privately held. The result of our computation is the length of the path and/or the path composition; the parties can then decide whether these are disclosed. Moreover, it can offer perfect securityFootnote 1 and its multiplicative complexity i.e. round complexity, is one order of magnitude lower than the current state of the art [2, 4].

1.1 Related Work

Aly et al. [2, 4] have introduced several data-oblivious protocols to solve the SPP, including adaptations of Dijkstra. However, their complexity bound on the number of sequential multiplications is cubic, whereas we only require a quadratic number of such multiplications. Brickell and Shmatikov [8] introduced a protocol for the SPP in a two-party setting against semi-honest adversaries. In contrast, our solution is not limited to the two-party case and also provides security against active adversaries. The Breadth-First-Search (BFS) proposed by Blanton et al. [7] provides complexity bounds for a special case of the SPP i.e. non-weighted graph. Conversely, we consider the general case where the graph is weighted. Furthermore, Keller and Scholl [17] implemented Dijkstra’s algorithm using Oblivious RAM (ORAM) based data-structures matching the \(\mathcal {O}(|V|^2)\) complexity of the original algorithm. However, their results show that for certain graph sizes, Aly et al. [2] can out-perform their ORAM-based implementation, as ORAM’s intrinsic overhead exceeds any asymptotic advantage.

1.2 Notation and Security

We make use of the square brackets notation for secret shared values e.g. \([\![ x ]\!]\). Furthermore, we consider all inputs to be elements of \(\mathbb {Z}_{q}\), where q is a sufficiently largeFootnote 2 prime or RSA modulus. Complexity is measured in terms of round complexity (multiplicative depth or latency) of the whole protocol. Vectors and matrices are represented by capital letters e.g. E, where |E| denotes its size. Finally, some common encapsulations used throughout our protocols are denoted as follows:

  • \([\![ z ]\!]\leftarrow _{[\![ c ]\!]}[\![ x ]\!]:[\![ y ]\!]\) is the conditional operator. It can be seen as an arithmetic replacement for the if branching instruction. Here, \([\![ c ]\!]\) represents a selection bit and \([\![ z ]\!]\) takes the value of \([\![ x ]\!]\) if \([\![ c ]\!]{\mathop {==}\limits ^{?}}1\) and \([\![ y ]\!]\) otherwise. This simple construction requires only one communication round i.e. \([\![ c ]\!]\cdot ([\![ x ]\!]-[\![ y ]\!]) + [\![ y ]\!]\).

  • exchange\((i,j,[\![ X ]\!])\) swaps the elements in the i-th and j-th position of vector X. This operation is not cryptographic in nature.

Security of MPC protocols is typically defined in the context of simulation under the UC framework [9, 10]. To simplify the analysis, we abstract the required MPC ideal functionality as an arithmetic black box or \(\mathcal {F}_{ABB} \). Initially introduced by Damgård and Nielsen [13], it can be extended to support other ideally modeled functionality e.g. secure comparisons. We offer a revision of our \(\mathcal {F}_{ABB}\), including corresponding UC secure realizations in Table 1. We proceed to define security as follows:

Definition 1

Let \(\pi _{\texttt {SP}}\) be a real protocol implemented in a multiparty setting. We say \(\pi _{\texttt {SP}}\) is UC-secure if, for any adversary \(\mathscr {A}\), there exists a simulator \(\mathscr {S}\) such that the \(\texttt{VIEW}_{\pi }(P_{i})\) of any party \(P_{i}\) interacting with the environment \(\mathscr {Z}\), cannot be distinguished (with non-negligible probability) between the real protocol \(\pi _{\texttt {SP}}\) and the ideal functionality \(\mathcal {F}_{\textit{SP}}\).

Table 1. Secure Arithmetic operations provided by the \(\mathcal {F}_{ABB} \).
Full size table

2 Privacy Preserving Single Source SPP

Let \(G = (V,E)\) be a directed graph without negative cycles where V is the set of vertices and E is the set of edges. Furthermore, G is represented as a weighted adjacency matrix \([\![ U ]\!]\) where \([\![ U ]\!]_{ij}\) is the weight of edge (i, j) \( \forall (i,j) \in E\). The intuition underlying our protocol is as follows: \([\![ U ]\!]\) is obliviously permuted before protocol execution. We then assign temporary labels to each vertex in G (i.e. each row in \([\![ U ]\!]\)). Our protocol then proceeds to identify the most suitable vertex to explore. However, unlike other works in the field, given the permutation, we are able to open the next vertex temporary label and directly explore it. Note that the label itself does not convey any information other than the position of the row in the now permuted matrix \([\![ U ]\!]\).

figure a

Complexity: Our protocol requires \(\mathcal {O}(|V|^2 \cdot log(|V|))\) secure multiplications (amount of work). Such multiplications can be parallelized achieving \(\mathcal {O}(|V|^2)\) rounds of communication. Furthermore, Protocol 1 contains two additional multiplications in line 17 and 18, which can also be parallelized. The exchange operation does not influence the complexity of the protocol, as it is done over publicly available information.

Security Analysis: Our protocol does not disclose any private information during its execution. More precisely, the call to \(\texttt{open}([v])\) (in line 12 of Protocol 1) does not reveal the original index position of the analyzed vertex, since the vertices are uniformly (and obliviously) permuted. The Achievable Security of our protocol is the same as that of the underlying MPC protocol e.g. we can achieve perfect security assuming honest majorities for the active and passive case [6]; or cryptographic security assuming dishonest majorities for the active and passive case as in(but not limited to) [5] or any SPDZ variation. More formally, we proceed to define our ideal functionality as follows:

Definition 2

(Ideal Functionality \(\mathcal {F}_{\textit{SP}}\)). Let \(G=(V,E)\) be a connected directed graph. Let the elements of the weighted adjacent matrix U and the source vertex s be elements of \(\mathbb {Z}_{q}\), and let both be privately held inputs. The ideal functionality \(\mathcal {F}_{SP}\) receives both \([\![ U ]\!]\) and \([\![ s ]\!]\) and returns the shortest path \([\![ \alpha ]\!]\) and the distances \([\![ D ]\!]\) via the \(\mathcal {F}_{ABB}\), whilst opening \([\![ v ]\!]\) at every cycle.

We now proceed to prove security for Protocol 1 (denoted as \(\pi _{\texttt {SP}}\)) as follows:

Theorem 1

The protocol \(\pi _{\texttt {SP}}\) securely implements \(\mathcal {F}_{\texttt {SP}}\) in the \(\mathcal {F}_{\textit{ABB}}\) framework.

Proof

The disclosed intermediate values v do not convey any information to the adversary i.e. Are indexes of the permuted matrix. Furthermore, the protocol flow only depends on publicly available values i.e. the upper bound on the number of vertices and the v values. The simulation of the complete protocol can be achieved by calling the \(\mathcal {F}_{ABB}\) functionality available for the atomic operations in the order fixed by the protocol flow. Since the real and ideal views for the atomic operations are themselves equal (as they are implemented by the \(\mathcal {F}_{ABB} \)), \(\texttt{VIEW}_{\pi _{SP}}(P_{i}) \equiv \texttt{VIEW}_{\mathcal {F}_{\texttt {SP}}}(P_{i})\), \(\forall \ \ P_i \in P\) where P is the set of all parties. Hence, we can argue the same for the Environment \(\mathscr {Z}\). \(\square \)

3 Computational Experiments

We built our prototype and conducted extensive experiments via the commonly used framework SCALE-MAMBA  [1]. This circuit compiler and virtual execution environment, provides users with the means to run different adversarial settings and protocols. For the case at hand, we consider the reduced communication protocol based on Shamir by Smart and Wood [19] (honest majorities) and, Overdrive [16] with TopGear [5], members of the SPDZ protocol family (Full Threshold). Both provide active security. Additionally, we assume a lookup table style permutation [14, 15] (amortized). We have made our prototype fully available as opensourceFootnote 3 so that it can be further used as subroutine in other programs.

Test bed Configuraiton: Our setup consists on 5 Ubuntu 18 servers on premise. Each one has been allocated with 512 GB in RAM memory and a Intel(R) Xeon(R) Silver 4208 @ 2.10 GH CPU. Servers are connected using Gigabit LAN connections, with a ping time of 0.15 ms in average. This way, we can control network latency via /sbin/tc.

Table 2. Performance evaluation (ms) with 2/3 machines (FT / Shamir)
Full size table

As we can see, communications dominate complexity, hence the importance of reducing communication rounds. On benchmarking, we can appreciate how the delta, with the previous state of the art, becomes more significant when the number of vertices increases following the asymptotic complexity. We point out that further experimentation showed a similar decrease of computational cost when the graph structure is public. Note that modern compilers also use a variety of instruction optimizers to accelerate online performance e.g. parallelize non-linearities that are non-sequential. Its use however becomes prohibitive for large scale circuits. In such cases, our experimentation also shows a similar increase on performance.