Paper 2017/296

Topology-Hiding Computation on all Graphs

Adi Akavia, Rio LaVigne, and Tal Moran

Abstract

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.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint. MINOR revision.
Keywords
topology-hidingtopology-hiding computationbroadcast
Contact author(s)
rio @ mit edu
History
2018-01-24: last of 4 revisions
2017-04-03: received
See all versions
Short URL
https://ia.cr/2017/296
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/296,
      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{https://eprint.iacr.org/2017/296}},
      url = {https://eprint.iacr.org/2017/296}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.