Cryptology ePrint Archive: Report 2017/393

Privacy-Preserving Interdomain Routing at Internet Scale

Gilad Asharov and Daniel Demmler and Michael Schapira and Thomas Schneider and Gil Segev and Scott Shenker and Michael Zohner

Abstract: 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 3s 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.

Category / Keywords: implementation / BGP; secure multi-party computation;

Original Publication (with minor differences): Proceedings on Privacy Enhancing Technologies (PoPETs) 2017.3

Date: received 5 May 2017

Contact author: daniel demmler at cysec de

Available format(s): PDF | BibTeX Citation

Version: 20170509:121303 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]