Cryptology ePrint Archive: Report 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 o ers 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 eciency of our protocol by experiments and benchmarking.

Category / Keywords: shortest path problem, combinatorial auctions, secure multi-party computation

Date: received 3 Oct 2017, last revised 18 Oct 2017

Contact author: abdelrahaman aly at esat kuleuven be

Available format(s): PDF | BibTeX Citation

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

Version: 20171018:103426 (All versions of this report)

Short URL: ia.cr/2017/971

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]