larly send messages (sending dummies
when the users are not involved in a
conversation). This approach, which
is taken by state-of-the-art systems,
induces significant cost to battery life
and data-plans when running on mobiles. To support mobile clients used
by a massive portion of the Internet’s
users, it seems necessary to rethink
Reducing computations. The recent
horizontally scalable designs distribute the communication overhead over
many contributing organizations.
The state-of-the-art systems, however, make extensive use of public key
cryptography and rely on hefty cryptographic protocols like zero-knowledge
proofs of shuffle and correct decryp-tion. In particular, the performance of
the horizontally scalable systems in the
table—Karaoke and Pung—is bounded by computations (see experimental
evaluation. 1, 19). Finding a way to minimize the use of these cryptographic
constructs, such as by establishing persistent private sessions and using sym-metric-key cryptography within these
sessions (as often done when hiding
content), would alleviate the computational bottleneck and reduce communication latency significantly.
Improving the topology. It is common to route messages through servers operated by organizations in
different political and geographic regions, to reduce the chance that the
organizations administrating these
servers would collude or coerced to
expose secrets. Topology studies were
performed mostly on Tor, to avoid
routing through specific autonomous
systems16, 25 (combating the attacks
mentioned previously) and to avoid
overloading specific relays. 15
A largely remaining challenge is
to optimize the route that messages
would take through different geograph-
ic regions, so as to avoid sending mes-
sages through an overly long distance.
A route with many distant randomly
selected hops18, 19, 35, 36 means that even if
each server only relays a small portion
of the messages, and does not perform
any computationally heavy processing,
the aggregate of the interserver laten-
cies might be too expensive to support
some applications. A significant chal-
lenge in supporting latency-sensitive
applications is therefore to identify
better routing topologies, which allow
to mix all messages for privacy, yet do
not require messages to go through
many hops for performance.
The author thanks Sharon Goldberg,
David Lazar, Michael Schapira, Adam
Suhl, Moshe Vardi, Nickolai Zeldovich,
and the anonymous reviewers for their
helpful comments on earlier versions
of this article.
1. Angel, S. and T. V. Setty, S. Unobservable
communication over fully untrusted infrastructure. In
Proceedings of OSDI, 2016. K. Keeton and T. (Eds.).
USENIX Assoc., 551–569.
2. Aryan, S., Aryan, H. and Halderman, J.A. Internet
censorship in Iran: A first look. In Proceedings
of FOCI, 2013. J. R. Crandall and J. Wright (Eds.).
3. Corrigan-Gibbs, H., Boneh, D. and Mazières, D. Riposte:
An anonymous messaging system handling millions of
users. In Proceedings of IEEE Symposium on Security
and Privacy, 2015. IEEE Computer Society, 321–338;
4. Cowie, J. New Threat: Targeted Internet Traffic
5. Das, D., Meiser, S., Mohammadi, E. and Kate, A.
Anonymity trilemma: Strong anonymity, low
bandwidth, low latency—Choose two. In Proceedings
of Security and Privacy. IEEE, 2018.
6. Dingledine, R. and Mathewson, N. Anonymity
loves company: Usability and the network effect.
In Proceedings of Workshop on the Economics of
Information Security, 2006.
7. Dingledine, R., Mathewson, N. and Syverson, P.F. Tor:
The second-generation onion router. In Proceedings
of USENIX Security Symposium, 2004. M. Blaze (Ed.).
8. Dwork, C., McSherry, F., Nissim, K. and Smith, A. D.
Calibrating noise to sensitivity in private data analysis.
TCC 3876 (2006). Springer, 265–284.
9. Erlingsson, U., Pihur, V., and Korolova, A. RAPPOR:
Randomized aggregatable privacy-preserving ordinal
response. In Proceedings of ACM Conf. Computer and
Communications Security, 2014. G.-J. Ahn, M. Yung,
and N. Li (Eds.). ACM, 1054–1067; http://dl.acm.org/
10. Finley, K. Half of the Internet is now encrypted.
This makes everyone safer; https://www.
11. Gilad, Y. and Herzberg, A. Spying in the dark: TCP and
Tor traffic analysis. Privacy Enhancing Technologies,
LNCS 7384 (2012). S. Fischer-Hübner and M. K. Wright
(Eds.). Springer, 100–119.
12. Greenwald, G. and MacAskill, E. NSA Prism program
taps in to user data of Apple, Google and others;
13. Hayden, M. The price of privacy: Re-evaluating the
NSA. Proceedings of the Johns Hopkins Foreign Affairs
Symposium. (Apr. 2014); https://www.youtube.com/
14. Apple, Inc. Differential Privacy, 2016; https://www.
15. Johnson, A., Jansen, R., Hopper, N., Segal, A. and
Syverson, P. PeerFlow: Secure load balancing in Tor.
Proceedings of PoPETs 2 (2017), 74–94.
16. Johnson, A., Wacek, C., Jansen, R., Sherr, M. and
Syverson, P. Users get routed: Traffic correlation on
Tor by realistic adversaries. In Proceedings of ACM
Conf. Computer and Communications Security, 2013
A-R Sadeghi, V.D. Gligor and M. Yung (Eds.). ACM,
17. Khattak, S. et al. Do you see what I see? Differential
treatment of anonymous users. In Proceedings
of NDSS, 2016. The Internet Society; https://bit.
18. Kwon, A., Corrigan-Gibbs, H., Devadas, S. and Ford,
B. Atom: Horizontally scaling strong anonymity. In
Proceedings of SOSP, 2017. ACM, 406–422; http://
19. Lazar, D., Gilad, Y. and Zeldovich, N. Karaoke: Fast
and strong metadata privacy with low noise. In
Proceedings of OSDI, 2018. USENIX Assoc.
20. Lazar, D. and Zeldovich, N. Alpenhorn: Bootstrapping
secure communication without leaking metadata. In
Proceedings of OSDI, 2016. K. Keeton and T. Roscoe
(Eds.). USENIX Assoc., 571–586.
21. Levine, B. N., Reiter, M. K., Wang, C. and Wright, M. K.
2004. Timing attacks in low-latency mix systems
(extended abstract). Financial Cryptography LNCS,
3110. A. Juels (Ed.). Springer, 251–265.
22. Microsoft. 2 Billion Minutes a Day! Skype blog; https://
23. Moghaddam, H. M., Li, B., Derakhshani, M., and
Goldberg, I. SkypeMorph: Protocol obfuscation for Tor
bridges. In Proceedings of ACM Conf. Computer and
Communications Security. T. Yu, G. Danezis, and V. D.
Gligor (Eds.). ACM, 97–108; http://dl.acm.org/citation.
24. National Security Agency. Tor stinks. The Guardian.
(Oct. 2013); https://bit.ly/2Qzntb7.
25. Nithyanand, R., Singh, R., Cho, S. and Gill, P. Holding all
the ASes: Identifying and circumventing the pitfalls of
AS-aware Tor client design. CoRR, 2016; http://arxiv.
26. Nithyanand, R., Starov, O., Gill, P., Zair, A. and Schapira,
M. Measuring and mitigating AS-level adversaries
against Tor. In Proceedings of NDSS, 2016. The
Internet Society; https://bit.ly/2wqK54o
27. Piotrowska, A.M., Hayes, J., Elahi, T., Meiser, S.
and Danezis, G. The Loopix anonymity system. In
Proceedings of USENIX Security Symposium, 2017.
E. Kirda and T. Ristenpart (Eds.). USENIX Assoc.,
28. Rusbridger, A. The Snowden leaks and the public;
29. Singh, R. et al. Characterizing the nature and dynamics
of Tor exit blocking. In Proceedings of USENIX
Security Symposium, 2017. E. Kirda and T. Ristenpart,
(Eds.). USENIX Assoc., 325–341.
30. Statistica, the statistics portal. Average monthly
outbound mobile voice minutes per person in the
United Kingdom (UK) from 2008 to 2013 (in minutes).
31. Sun, Y. et al. RAPTOR: Routing attacks on privacy in
Tor. In Proceedings of USENIX Security Symposium,
2015. J. Jung and T. Holz (Eds.). USENIX Assoc.,
32. Telegram. 15 Billion Telegrams Delivered Daily.
Telegram announcement, 2017; https://telegram.org/
33. The Tor project. Pluggable Transports, 2017; https://
34. Tung, L. WhatsApp: Now one billion people send 55
billion messages per day, 2017; http://www.zdnet.com/
35. Tyagi, N., Gilad, Y., Leung, E., Zaharia, M. and Zeldovich,
N. Stadium: A distributed metadata-private messaging
system. In Proceedings of SOSP, 2017. ACM,
36. Hooff, J., Lazar, D., Zaharia, M. and Zeldovich, N.
Vuvuzela: Scalable private messaging resistant to
traffic analysis. In Proceedings of SOSP, 2015. E.L.
Miller and S. Hand (Eds.). ACM, 137–152; http://dl.acm.
37. Weinberg, Z. et al. Stego Torus: A camouflage proxy
for the Tor anonymity system. In Proceedings of ACM
Conf. on Computer and Communications Security,
2012. T. Yu, G. Danezis and V. D. Gligor (Eds.). ACM,
38. Winter, P. and Lindskog, S. How the great firewall of
China is blocking Tor. In Proceedings of FOCI, 2012. R.
Dingledine and J. Wright (Eds.). USENIX Assoc.
39. Wolinsky, D.I., Corrigan-Gibbs, H., Ford, B. and Johnson,
A. dissent in numbers: Making strong anonymity scale.
In Proceedings of OSDI, 2012. C. Thekkath and A.
Vahdat (Eds.). USENIX Assoc., 179–182.
40. Zmijewski, E. Indonesia Hijacks the World, 2013;
Yossi Gilad is Senior Lecturer at the Hebrew University of
©2019 ACM 0001-0782/19/9 $15.00.