Welcome to the resource topic for 2024/1266
Title:
Information-Theoretic Topology-Hiding Broadcast: Wheels, Stars, Friendship, and Beyond
Authors: D'or Banoun, Elette Boyle, Ran Cohen
Abstract:Topology-hiding broadcast (THB) enables parties communicating over an incomplete network to broadcast messages while hiding the network topology from within a given class of graphs. Although broadcast is a privacy-free task, it is known that THB for certain graph classes necessitates computational assumptions, even against “honest but curious” adversaries, and even given a single corrupted party. Recent works have tried to understand when THB can be obtained with information-theoretic (IT) security (without cryptography or setup assumptions) as a function of properties of the corresponding graph class.
We revisit this question through a case study of the class of wheel graphs and their subgraphs. The n'th wheel graph is established by connecting n nodes who form a cycle with another “center” node, thus providing a natural extension that captures and enriches previously studied graph classes in the setting of IT-THB.
We present a series of new findings in this line.
We fully characterize feasibility of IT-THB for any class of subgraphs of the wheel, each possessing an embedded star (i.e., a well-defined center connected to all other nodes). Our characterization provides evidence that IT-THB feasibility may correlate with a more fine-grained degree structure—as opposed to pure connectivity—of the corresponding graphs.
We provide positive results achieving perfect IT-THB for new graph classes, including ones where the number of nodes is unknown. Further, we provide the first feasibility of IT-THB on non-degenerate graph-classes with t>1 corruptions, for the class of friendship graphs (Erdos, Renyi, Sos '66).
ePrint: https://eprint.iacr.org/2024/1266
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .