Paper 2017/971

An Improved Protocol for Securely Solving the Shortest Path Problem and its Application to Combinatorial Auctions

Abdelrahaman Aly and Sara Cleemput

Abstract

We propose a protocol to securely compute the solution to the (single source) Shortest Path Problem, based on Dijkstra's algorithm and Secure Multiparty Computation. Our protocol improves state of the art by Aly et al. [FC 2013 & ICISC 2014] and offers perfect security against both semi-honest and malicious adversaries. Moreover, it can easily be adapted to form a subroutine in other combinatorial mechanisms and we show how it can help solve certain combinatorial auctions. Finally, we demonstrate the efficiency of our protocol by experiments and benchmarking.

Note: Erros found on Figures and typos and redaction issues on the security proof. I this version we Updated the Figures and Security Proof.