Paper 2024/1266
Information-Theoretic Topology-Hiding Broadcast: Wheels, Stars, Friendship, and Beyond
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).
Metadata
- Available format(s)
-
PDF
- Category
- Cryptographic protocols
- Publication info
- Published elsewhere. Major revision. ITC 2024
- DOI
- 10.4230/LIPICS.ITC.2024.1
- Keywords
- Topology-hiding broadcastsecure multiparty computationwheel graphstar graphfriendship graph
- Contact author(s)
-
dor banoun @ post runi ac il
elette boyle @ runi ac il
cohenran @ runi ac il - History
- 2024-08-12: approved
- 2024-08-09: received
- See all versions
- Short URL
- https://ia.cr/2024/1266
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2024/1266, author = {D'or Banoun and Elette Boyle and Ran Cohen}, title = {Information-Theoretic Topology-Hiding Broadcast: Wheels, Stars, Friendship, and Beyond}, howpublished = {Cryptology {ePrint} Archive, Paper 2024/1266}, year = {2024}, doi = {10.4230/LIPICS.ITC.2024.1}, url = {https://eprint.iacr.org/2024/1266} }