Network-Hiding Communication and Applications to Multi-Party Protocols

Martin Hirt, Ueli Maurer, Daniel Tschudi, Vasileios Zikas

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract / Description of output

As distributed networks are heavily used in modern applications, new security challenges emerge. In a multi-party computation (in short, MPC) protocol over an incomplete network, such a challenge is to hide, to the extent possible, the topology of the underlying communication network. Such a topology-hiding (aka network hiding) property is in fact very relevant in applications where anonymity is needed.

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.
Original languageEnglish
Title of host publicationAdvances in Cryptology – CRYPTO 2016
Number of pages31
ISBN (Electronic)978-3-662-53008-5
ISBN (Print)978-3-662-53007-8
Publication statusPublished - 21 Jul 2016
Event36th Annual International Cryptology Conference - University of California, Santa Barbara, United States
Duration: 14 Aug 201618 Aug 2016

Publication series

NameLecture Notes in Computer Science
PublisherSpringer, Berlin, Heidelberg
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference36th Annual International Cryptology Conference
Abbreviated titleCRYPTO 2016
Country/TerritoryUnited States
CitySanta Barbara
Internet address


Dive into the research topics of 'Network-Hiding Communication and Applications to Multi-Party Protocols'. Together they form a unique fingerprint.

Cite this