Paper 2017/296

Topology-Hiding Computation on all Graphs

Adi Akavia, Rio LaVigne, and Tal Moran


A distributed computation in which nodes are connected by a partial communication graph is called topology-hiding if it does not reveal information about the graph beyond what is revealed by the output of the function. Previous results have shown that topology-hiding computation protocols exist for graphs of constant degree and logarithmic diameter in the number of nodes [Moran-Orlov-Richelson, TCC'15; Hirt \etal, Crypto'16] as well as for other graph families, such as cycles, trees, and low circumference graphs [Akavia-Moran, Eurocrypt'17], but the feasibility question for general graphs was open. In this work we positively resolve the above open problem: we prove that topology-hiding computation is feasible for all graphs under either the Decisional Diffie-Hellman or Quadratic-Residuosity assumption. Our techniques employ random-walks to generate paths covering the graph, upon which we apply the Akavia-Moran topology-hiding broadcast for chain-graphs (paths). To prevent topology information revealed by the random-walk, we design multiple random-walks that, together, are locally identical to receiving at each round a message from each neighbors and sending back processed messages in a randomly permuted order.

Note: We have a few new results, including being able to use an additional assumption (QR) to get topology-hiding computation, and the use of more general exploration sequences instead of random walks in our protocol.

Available format(s)
Cryptographic protocols
Publication info
Preprint. MINOR revision.
topology-hidingtopology-hiding computationbroadcast
Contact author(s)
rio @ mit edu
2018-01-24: last of 4 revisions
2017-04-03: received
See all versions
Short URL
Creative Commons Attribution


      author = {Adi Akavia and Rio LaVigne and Tal Moran},
      title = {Topology-Hiding Computation on all Graphs},
      howpublished = {Cryptology ePrint Archive, Paper 2017/296},
      year = {2017},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.