A Fast, Practical and Simple Shortest Path Protocol for Multiparty Computation

Abdelrahaman Aly; Sara Cleemput

Paper 2017/971

A Fast, Practical and Simple Shortest Path Protocol for Multiparty Computation

Abdelrahaman Aly

Sara Cleemput

Abstract

We present a simple and fast protocol to securely solve the (single source) Shortest Path Problem, based on Dijkstra's algorithm over Secure Multiparty Computation. Our protocol improves current state of the art by Aly et al. [FC 2013 & ICISC 2014] and can offer perfect security against both semi-honest and malicious adversaries. Furthermore, it is the first data oblivious protocol to achieve quadratic complexity in the number of communication rounds. Moreover, our protocol can be easily be adapted to form a subroutine in other combinatorial mechanisms. Our focus is usability; hence, we provide an open source implementation and exhaustive benchmarking under different adversarial settings and players setups.

Note: Final Accepted version before camera Ready in Esorics. Updated Experimentation. Scratched Application

Metadata

Available format(s): PDF
Category: Applications
Publication info: Published elsewhere. ESORICS 2022
Keywords: shortest path problem applied cryptography secure multi-party computation
Contact author(s): Abdelrahaman aly @ gmail com
History: 2022-08-11: last of 5 revisions; 2017-10-05: received; See all versions
Short URL: https://ia.cr/2017/971
License: CC BY

BibTeX

@misc{cryptoeprint:2017/971,
      author = {Abdelrahaman Aly and Sara Cleemput},
      title = {A Fast, Practical and Simple Shortest Path Protocol for Multiparty Computation},
      howpublished = {Cryptology {ePrint} Archive, Paper 2017/971},
      year = {2017},
      url = {https://eprint.iacr.org/2017/971}
}