2020/06/19 by Miklós Z. Rácz, Racz, Miklos Z., Jacob Richey +1
Computer Science · #Cryptography and Security (cs.CR) #FOS: Computer and information sciences #FOS: Mathematics #Internet Traffic Analysis and Secure E-voting #Privacy-Preserving Technologies in Data #Probability (math.PR) #Social and Information Networks (cs.SI) #Spam and Phishing Detection #Statistics Theory (math.ST)
paper · pdf · doi:10.48550/arxiv.2006.11211
openalex publication_date 2020/06/19 · openalex created_date 2022/07/26 · openalex updated_date 2026/07/28
Recent work, motivated by anonymous messaging platforms, has introduced\nadaptive diffusion protocols which can obfuscate the source of a rumor: a\n"snapshot adversary" with access to the subgraph of "infected" nodes can do no\nbetter than randomly guessing the entity of the source node. What happens if\nthe adversary has access to multiple independent snapshots? We study this\nquestion when the underlying graph is the infinite d-regular tree. We show\nthat (1) a weak form of source obfuscation is still possible in the case of two\nindependent snapshots, but (2) already with three observations there is a\nsimple algorithm that finds the rumor source with constant probability,\nregardless of the adaptive diffusion protocol. We also characterize the\ntradeoff between local spreading and source obfuscation for adaptive diffusion\nprotocols (under a single snapshot). These results raise questions about the\nrobustness of anonymity guarantees when spreading information in social\nnetworks.\n