Paper 2018/255

Topology-Hiding Computation Beyond Semi-Honest Adversaries

Rio LaVigne, Chen-Da Liu-Zhang, Ueli Maurer, Tal Moran, Marta Mularczyk, and Daniel Tschudi

Abstract

Topology-hiding communication protocols allow a set of parties, connected by an incomplete network with unknown communication graph, where each party only knows its neighbors, to construct a complete communication network such that the network topology remains hidden even from a powerful adversary who can corrupt parties. This communication network can then be used to perform arbitrary tasks, for example secure multi-party computation, in a topology-hiding manner. Previously proposed protocols could only tolerate passive corruption. This paper proposes protocols that can also tolerate fail-corruption (i.e., the adversary can crash any party at any point in time) and so-called semi-malicious corruption (i.e., the adversary can control a corrupted party's randomness), without leaking more than an arbitrarily small fraction of a bit of information about the topology. A small-leakage protocol was recently proposed by Ball et al. [Eurocrypt'18], but only under the unrealistic set-up assumption that each party has a trusted hardware module containing secret correlated pre-set keys, and with the further two restrictions that only passively corrupted parties can be crashed by the adversary, and semi-malicious corruption is not tolerated. Since leaking a small amount of information is unavoidable, as is the need to abort the protocol in case of failures, our protocols seem to achieve the best possible goal in a model with fail-corruption. Further contributions of the paper are applications of the protocol to obtain secure MPC protocols, which requires a way to bound the aggregated leakage when multiple small-leakage protocols are executed in parallel or sequentially. Moreover, while previous protocols are based on the DDH assumption, a new so-called PKCR public-key encryption scheme based on the LWE assumption is proposed, allowing to base topology-hiding computation on LWE. Furthermore, a protocol using fully-homomorphic encryption achieving very low round complexity is proposed.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published by the IACR in TCC 2018
Keywords
topology-hidingbroadcasttopology-hiding computationfail-stopsemi-malicious
Contact author(s)
lichen @ inf ethz ch
History
2018-10-26: revised
2018-03-07: received
See all versions
Short URL
https://ia.cr/2018/255
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/255,
      author = {Rio LaVigne and Chen-Da Liu-Zhang and Ueli Maurer and Tal Moran and Marta Mularczyk and Daniel Tschudi},
      title = {Topology-Hiding Computation Beyond Semi-Honest Adversaries},
      howpublished = {Cryptology ePrint Archive, Paper 2018/255},
      year = {2018},
      note = {\url{https://eprint.iacr.org/2018/255}},
      url = {https://eprint.iacr.org/2018/255}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.