Paper 2017/130

Topology-Hiding Computation Beyond Logarithmic Diameter

Adi Akavia and Tal Moran

Abstract

A distributed computation in which nodes are connected by a partial communication graph is called \emph{topology-hiding} if it does not reveal information about the graph (beyond what is revealed by the output of the function). Previous results [Moran, Orlov, Richelson; TCC'15] have shown that topology-hiding computation protocols exist for graphs of logarithmic diameter (in the number of nodes), but the feasibility question for graphs of larger diameter was open even for very simple graphs such as chains, cycles and trees. In this work, we take a step towards topology-hiding computation protocols for arbitrary graphs by constructing protocols that can be used in a large class of {\em large-diameter networks}, including cycles, trees and graphs with logarithmic \emph{circumference}. Our results use very different methods from [MOR15] and can be based on a standard assumption (such as DDH).

Metadata
Available format(s)
PDF
Publication info
Published by the IACR in EUROCRYPT 2017
Keywords
topology hiding multi party computationbroadcastvoting
Contact author(s)
akavia @ mta ac il
talm @ idc ac il
History
2017-02-16: received
Short URL
https://ia.cr/2017/130
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/130,
      author = {Adi Akavia and Tal Moran},
      title = {Topology-Hiding Computation Beyond Logarithmic Diameter},
      howpublished = {Cryptology ePrint Archive, Paper 2017/130},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/130}},
      url = {https://eprint.iacr.org/2017/130}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.