2026-07-24T00:34:43Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:20509 2024-08-06T05:20:07Z ddc:004 open_access

Information-Theoretic Topology-Hiding Broadcast: Wheels, Stars, Friendship, and Beyond Banoun, D'or Boyle, Elette Cohen, Ran broadcast topology-hiding protocols information-theoretic security 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 nth 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 (Erdös, Rényi, Sós '66). Schloss Dagstuhl – Leibniz-Zentrum für Informatik D'or Banoun and Elette Boyle and Ran Cohen 2024 Is Part Of LIPIcs, Volume 304, 5th Conference on Information-Theoretic Cryptography (ITC 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITC.2024.1 urn:nbn:de:0030-drops-205090 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2024.1 eng https://creativecommons.org/licenses/by/4.0/legalcode