To our knowledge, with the exception of two recent works by Chandran et al. [ITCS 2015] and by Moran et al. [TCC 2015], existing MPC protocols do not hide the topology of the underlying communication network. Moreover, the above two solutions are either not applicable to arbitrary networks (as is [ITCS 2015]) or, as in [TCC 2015], they make non-black-box and recursive use of cryptographic primitives resulting in an unrealistic communication and computation complexity even for simple, i.e., low degree and diameter, networks.
Our work suggests the first topology-hiding communication protocol for incomplete networks which makes black-box use of the underlying cryptographic assumption-in particular, a public-key encryption scheme-and tolerates any adversary who passively corrupts arbitrarily many network nodes. Our solutions are based on a new, enhanced variant of threshold homomorphic encryption, in short, TH-PKE, that requires no a-priori setup and allows to circulate an encrypted message over any (unknown) incomplete network and then decrypt it without revealing any network information to intermediate nodes. We show how to realize this enhanced TH-PKE from the DDH assumption. The black-box nature of our scheme, along with some optimization tricks that we employ, makes our communication protocol more efficient than existing solutions.
We then use our communication protocol to make any semi-honest secure MPC protocol topology-hiding with a reasonable-i.e., for simple networks, polynomial with small constants-communication and computation overhead. We further show how to construct anonymous broadcast without using expensive MPCs to setup the original pseudonyms.Category / Keywords: network-hiding communication, secure multiparty computation, anonymity Original Publication (with major differences): IACR-CRYPTO-2016 Date: received 2 Jun 2016 Contact author: tschudid at inf ethz ch Available format(s): PDF | BibTeX Citation Version: 20160603:162007 (All versions of this report) Short URL: ia.cr/2016/556 Discussion forum: Show discussion | Start new discussion