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). This is important since in many cases the communication graph itself can contain sensitive information (e.g., the "friend graph" of Facebook, or vehicle-to-vehicle networks, where the graph depends on physical location).
Previous results have shown that topology-hiding computation protocols exist for graphs of logarithmic diameter (in the number of nodes), but the feasibility question for graphs of larger diameter was open even for very simple graphs such as chains, cycles and trees.
In this work, we take a step towards topology-hiding computation protocols for arbitrary graphs by constructing protocols that can be used in a large class of large-diameter networks,
including cycles, trees and graphs with logarithmic circumference. Our results use very different methods from previous works and can be based on a standard assumption (such as DDH).
Adi Akavia is a senior lecturer at the Tel-Aviv Yaffo Academic College at Tel-Aviv Jaffa Israel and a member of the Foundation & Application of Cryptography Theory (FACT) research center hosted by the IDC Herzliya.
Her research interests lie in cryptography, complexity, and algorithms, with focus on securing cryptosystems against theoretical and practical attacks, and on devising sub-linear algorithms for signal processing tasks.