Rio LaVigne: Topology Hiding Computation for All Graphs
Friday, March 2, 2018 - 10:30am to 12:00pm
Location:
Hewlett, G882
Speaker:
Rio LaVigne
Seminar group:
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 and the QR assumption against passive adversaries. 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. We can also extend this result to use deterministic walks (exploration sequences), opening up the possibility for a perfectly-complete topology hiding broadcast. Joint work with Adi Akavia 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 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 and the QR assumption against passive adversaries. 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. We can also extend this result to use deterministic walks (exploration sequences), opening up the possibility for a perfectly-complete topology hiding broadcast. Joint work with Adi Akavia and Tal Moran.
Time permitting, I will also discuss the next sequence of results: we can also get topology hiding computation for all graphs against fail-stop adversaries while leaking an arbitrarily small polynomial fraction of a bit.
This is based on joint work with Chen-Da Liu Zhang, Ueli Maurer, Tal Moran, Marta Mularczyk, and Daniel Tschudi.