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
Creative Commons Attribution
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},
      note = {\url{https://eprint.iacr.org/2017/971}},
      url = {https://eprint.iacr.org/2017/971}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.