Privacy-Preserving Interdomain Routing at Internet Scale

TitlePrivacy-Preserving Interdomain Routing at Internet Scale
Publication TypeConference Paper
AuthorsAsharov, G., Demmler D., Sachapira M., Schneider T., Segev G., Shenker S., & Zohner M.
Published inProceedings of PoPETs 2017

The Border Gateway Protocol (BGP) computes routes between the organizational networks that make up today’s Internet. Unfortunately, BGP suffers from deficiencies, including slow convergence, security problems, a lack of innovation, and the leakage of sensitive information about domains’ routing preferences. To overcome some of these problems, we revisit the idea of centralizing and using secure multi-party computation (MPC) for interdomain routing which was proposed by Gupta et al. (ACM HotNets’12). We implement two algorithms for interdomain routing with state-of-the-art MPC protocols. On an empirically derived dataset that approximates the topology of today’s Internet (55 809 nodes), our protocols take as little as 6 s of topology-independent precomputation and only 3 s of online time. We show, moreover, that when our MPC approach is applied at country/region-level scale, runtimes can be as low as 0.17 s online time and 0.20 s pre-computation time. Our results motivate the MPC approach for interdomain routing and furthermore demonstrate that current MPC techniques are capable of efficiently tackling real-world problems at a large scale.


We thank the anonymous reviewers
for their valuable feedback on our paper. This
work has been co-funded by the German Federal Ministry
of Education and Research (BMBF) and by the
Hessen State Ministry for Higher Education, Research
and the Arts (HMWK) within CRISP, and by the DFG
as part of projects S5 and E3 within the CRC 1119
CROSSING. The third author is supported by an ERC
Starting Grant and the Israel National Cyber Bureau.
This work was supported by a Junior Fellow award
from the Simons Foundation, by the European Union’s
7th Framework Program (FP7) via a Marie Curie Career
Integration Grant, by the European Union’s Horizon
2020 Framework Program (H2020) via an ERC
Grant (Grant No. 714253), by the Israel Science Foundation
(Grant No. 483/13), by the Israeli Centers of
Research Excellence (I-CORE) Program (Center No.
4/11), by the US-Israel Binational Science Foundation
(Grant No. 2014632), by NSF Grant No. 1420064, and
by a Google Faculty Research Award. Part of the work
was done while the first author was a post-doc at the
IBM TJ Watson Research Center, supported by NSF
Grant No. 1017660.

ICSI Research Group

Networking and Security