A Rudimentary Model for Low-Latency Anonymous Communication Systems

2017/11/03 by Yufan Zheng, Zheng, Yufan
Computer Science · #Cryptography and Data Security #Cryptography and Security (cs.CR) #Distributed #FOS: Computer and information sciences #Information Theory (cs.IT) #Internet Traffic Analysis and Secure E-voting #Parallel #Privacy-Preserving Technologies in Data #and Cluster Computing (cs.DC)

paper · pdf · doi:10.48550/arxiv.1711.01110

openalex publication_date 2017/11/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

In this paper we present a rudimentary model for low-latency anonymous communication systems. Specifically, we study distributed OR algorithm as an abstract of the system. Based on our model, we give several satisfactory lower bounds of anonymity leakage of a deterministic OR algorithm. Some of them reveal a trade-off between anonymity and communication complexity. For the randomized OR algorithm, we only give a relatively trivial but possibly tight lower bound when leaving out communication complexity. And we find the relationship between our model and some open case in the study of secret sharing scheme, if considering communication complexity.

Citations

• Locality in Distributed Graph Algorithms
• Untraceable electronic mail, return addresses, and digital pseudonyms
• On Computable Numbers, with an Application to the Entscheidungsproblem
• A Survey on Routing in Anonymous Communication Protocols
• The Byzantine Generals Problem

Related

• Quantitative Analysis of Information Leakage in Probabilistic and Nondeterministic Systems
• Using a Secret Key to Foil an Eavesdropper
• The Capacity of Anonymous Communications
• Fully Anonymous Shared Memory Algorithms
• Probabilistic Anonymity and Admissible Schedulers