Paper 2017/971 Original: eprint.iacr.org/2017/971 ↗
A Fast, Practical and Simple Shortest Path Protocol for Multiparty Computation
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.
Metadata
- Available format(s)
PDF- Category
- Applications
- Publication info
- Preprint.
- History
- 2022-08-11: last updated
- 2017-10-05: published
- Short URL
- https://ia.cr/2017/971
- License
- https://creativecommons.org/licenses/by/4.0/
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}
}