Topology-Hiding Computation on All Graphs
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...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Springer US
2021
|
| Online Access: | https://hdl.handle.net/1721.1/131498 |
| _version_ | 1811077036744114176 |
|---|---|
| author | Akavia, Adi LaVigne, Rio Moran, Tal |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Akavia, Adi LaVigne, Rio Moran, Tal |
| author_sort | Akavia, Adi |
| collection | MIT |
| description | 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 either the decisional Diffie–Hellman or quadratic residuosity assumption. Our techniques employ random or deterministic 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 graph-covering sequences that, together, are locally identical to receiving at each round a message from each neighbor and sending back a processed message from some neighbor (in a randomly permuted order). |
| first_indexed | 2024-09-23T10:36:53Z |
| format | Article |
| id | mit-1721.1/131498 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T10:36:53Z |
| publishDate | 2021 |
| publisher | Springer US |
| record_format | dspace |
| spelling | mit-1721.1/1314982023-12-22T20:34:29Z Topology-Hiding Computation on All Graphs Akavia, Adi LaVigne, Rio Moran, Tal Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory 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 either the decisional Diffie–Hellman or quadratic residuosity assumption. Our techniques employ random or deterministic 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 graph-covering sequences that, together, are locally identical to receiving at each round a message from each neighbor and sending back a processed message from some neighbor (in a randomly permuted order). 2021-09-20T17:17:19Z 2021-09-20T17:17:19Z 2019-03-15 2020-09-24T21:22:17Z Article http://purl.org/eprint/type/JournalArticle https://hdl.handle.net/1721.1/131498 en https://doi.org/10.1007/s00145-019-09318-y Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. International Association for Cryptologic Research application/pdf Springer US Springer US |
| spellingShingle | Akavia, Adi LaVigne, Rio Moran, Tal Topology-Hiding Computation on All Graphs |
| title | Topology-Hiding Computation on All Graphs |
| title_full | Topology-Hiding Computation on All Graphs |
| title_fullStr | Topology-Hiding Computation on All Graphs |
| title_full_unstemmed | Topology-Hiding Computation on All Graphs |
| title_short | Topology-Hiding Computation on All Graphs |
| title_sort | topology hiding computation on all graphs |
| url | https://hdl.handle.net/1721.1/131498 |
| work_keys_str_mv | AT akaviaadi topologyhidingcomputationonallgraphs AT lavignerio topologyhidingcomputationonallgraphs AT morantal topologyhidingcomputationonallgraphs |