**Topology-Hiding Computation on all Graphs**

*Adi Akavia and 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 et.al., 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 the Decisional Diffie-Hellman 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.

**Category / Keywords: **cryptographic protocols / topology-hiding, topology-hiding computation, broadcast

**Date: **received 31 Mar 2017, last revised 5 Jun 2017

**Contact author: **rio at mit edu

**Available format(s): **PDF | BibTeX Citation

**Note: **Updated notation to be more consistent throughout the paper and included a more formal proof of the main theorem.

**Version: **20170605:190619 (All versions of this report)

**Short URL: **ia.cr/2017/296

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]