Document Open Access Logo

On the Complexity of Anonymous Communication Through Public Networks

Authors Megumi Ando , Anna Lysyanskaya, Eli Upfal

PDF
Thumbnail PDF

File

LIPIcs.ITC.2021.9.pdf
  • Filesize: 0.86 MB
  • 25 pages

Document Identifiers

Author Details

Megumi Ando
  • MITRE, Bedford, MA, USA
Anna Lysyanskaya
  • Brown University, Providence, RI, USA
Eli Upfal
  • Brown University, Providence, RI, USA

Funding

Part of this work was funded by NSF award IIS-1247581 while Megumi was a graduate student at Brown University.

Cite As Get BibTex

Megumi Ando, Anna Lysyanskaya, and Eli Upfal. On the Complexity of Anonymous Communication Through Public Networks. In 2nd Conference on Information-Theoretic Cryptography (ITC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 199, pp. 9:1-9:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.ITC.2021.9

Abstract

Onion routing is the most widely used approach to anonymous communication online. The idea is that Alice wraps her message to Bob in layers of encryption to form an "onion" and routes it through a series of intermediaries. Each intermediary’s job is to decrypt ("peel") the onion it receives to obtain instructions for where to send it next. The intuition is that, by the time it gets to Bob, the onion will have mixed with so many other onions that its origin will be hard to trace even for an adversary that observes the entire network and controls a fraction of the participants, possibly including Bob. Despite its widespread use in practice, until now no onion routing protocol was known that simultaneously achieved, in the presence of an active adversary that observes all network traffic and controls a constant fraction of the participants, (a) anonymity; (b) fault-tolerance, where even if a few of the onions are dropped, the protocol still delivers the rest; and (c) reasonable communication and computational complexity as a function of the security parameter and the number of participants. 
In this paper, we give the first onion routing protocol that meets these goals: our protocol (a) achieves anonymity; (b) tolerates a polylogarithmic (in the security parameter) number of dropped onions and still delivers the rest; and (c) requires a polylogarithmic number of rounds and a polylogarithmic number of onions sent per participant per round. We also show that to achieve anonymity in a fault-tolerant fashion via onion routing, this number of onions and rounds is necessary. Of independent interest, our analysis introduces two new security properties of onion routing - mixing and equalizing - and we show that together they imply anonymity.

Subject Classification

ACM Subject Classification
  • Security and privacy → Security protocols
Keywords
  • Anonymity
  • privacy
  • onion routing

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Mário S. Alvim, Miguel E. Andrés, Konstantinos Chatzikokolakis, Pierpaolo Degano, and Catuscia Palamidessi. Differential privacy: on the trade-off between utility and information leakage. In FAST 2011, pages 39-54. Springer, 2011. Google Scholar
  2. Megumi Ando and Anna Lysyanskaya. Cryptographic shallots: A formal treatment of repliable onion encryption. IACR Cryptol. ePrint Arch., 2020:215, 2020. URL: https://eprint.iacr.org/2020/215.
  3. Megumi Ando, Anna Lysyanskaya, and Eli Upfal. Practical and provably secure onion routing. In Ioannis Chatzigiannakis, Christos Kaklamanis, Dániel Marx, and Donald Sannella, editors, ICALP 2018, volume 107 of LIPIcs, pages 144:1-144:14. Schloss Dagstuhl, July 2018. URL: https://doi.org/10.4230/LIPIcs.ICALP.2018.144.
  4. Michael Backes, Ian Goldberg, Aniket Kate, and Esfandiar Mohammadi. Provably secure and practical onion routing. In Computer Security Foundations Symposium (CSF), 2012 IEEE 25th, pages 369-385. IEEE, 2012. Google Scholar
  5. Michael Backes, Aniket Kate, Praveen Manoharan, Sebastian Meiser, and Esfandiar Mohammadi. Anoa: A framework for analyzing anonymous communication protocols. In Computer Security Foundations Symposium (CSF), 2013 IEEE 26th, pages 163-178. IEEE, 2013. Google Scholar
  6. Ron Berman, Amos Fiat, and Amnon Ta-Shma. Provable unlinkability against traffic analysis. In Ari Juels, editor, FC 2004, volume 3110 of LNCS, pages 266-280. Springer, Heidelberg, February 2004. Google Scholar
  7. Jan Camenisch and Anna Lysyanskaya. A formal treatment of onion routing. In Victor Shoup, editor, CRYPTO 2005, volume 3621 of LNCS, pages 169-187. Springer, Heidelberg, August 2005. URL: https://doi.org/10.1007/11535218_11.
  8. Ran Canetti. Universally composable security: A new paradigm for cryptographic protocols. In 42nd FOCS, pages 136-145. IEEE Computer Society Press, October 2001. URL: https://doi.org/10.1109/SFCS.2001.959888.
  9. Ran Canetti and Tal Rabin. Fast asynchronous byzantine agreement with optimal resilience. In Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, May 16-18, 1993, San Diego, CA, USA, pages 42-51. ACM, 1993. URL: https://doi.org/10.1145/167088.167105.
  10. Konstantinos Chatzikokolakis, Catuscia Palamidessi, and Prakash Panangaden. Anonymity protocols as noisy channels. Information and Computation, 206(2-4):378-401, 2008. Google Scholar
  11. David Chaum. Untraceable electronic mail, return addresses, and digital pseudonyms. Commun. ACM, 24(2):84-88, 1981. URL: https://doi.org/10.1145/358549.358563.
  12. David Chaum. The dining cryptographers problem: Unconditional sender and recipient untraceability. Journal of Cryptology, 1(1):65-75, January 1988. URL: https://doi.org/10.1007/BF00206326.
  13. Miranda Christ. New lower bounds on the complexity of provably anonymous onion routing. Undergraduate honors thesis, Brown University, Providence, RI 02912 USA, 2020. Google Scholar
  14. David A. Cooper and Kenneth P. Birman. Preserving privacy in a network of mobile computers. In 1995 IEEE Symposium on Security and Privacy, pages 26-38. IEEE Computer Society Press, 1995. URL: https://doi.org/10.1109/SECPRI.1995.398920.
  15. Henry Corrigan-Gibbs, Dan Boneh, and David Mazières. Riposte: An anonymous messaging system handling millions of users. In 2015 IEEE Symposium on Security and Privacy, pages 321-338. IEEE Computer Society Press, May 2015. URL: https://doi.org/10.1109/SP.2015.27.
  16. Ronald Cramer, Ivan Bjerre Damgård, and Jesper Buus Nielsen. Secure multiparty computation. Cambridge University Press, 2015. Google Scholar
  17. Debajyoti Das, Sebastian Meiser, Esfandiar Mohammadi, and Aniket Kate. Anonymity trilemma: Strong anonymity, low bandwidth overhead, low latency - choose two. In 2018 IEEE Symposium on Security and Privacy, pages 108-126. IEEE Computer Society Press, May 2018. URL: https://doi.org/10.1109/SP.2018.00011.
  18. Roger Dingledine, Nick Mathewson, and Paul F. Syverson. Tor: the second-generation onion router. In Proceedings of the 13th USENIX Security Symposium, August 9-13, 2004, San Diego, CA, USA, pages 303-320, 2004. Google Scholar
  19. Yevgeniy Dodis, Leonid Reyzin, and Adam Smith. Fuzzy extractors: How to generate strong keys from biometrics and other noisy data. In Christian Cachin and Jan Camenisch, editors, EUROCRYPT 2004, volume 3027 of LNCS, pages 523-540. Springer, Heidelberg, May 2004. URL: https://doi.org/10.1007/978-3-540-24676-3_31.
  20. Oded Goldreich. Foundations of Cryptography: Basic Tools, volume 1. Cambridge University Press, Cambridge, UK, 2001. Google Scholar
  21. Oded Goldreich, Silvio Micali, and Avi Wigderson. How to play any mental game or A completeness theorem for protocols with honest majority. In Alfred Aho, editor, 19th ACM STOC, pages 218-229. ACM Press, May 1987. URL: https://doi.org/10.1145/28395.28420.
  22. Don Hush and Clint Scovel. Concentration of the hypergeometric distribution. Statistics & Probability Letters, 75(2):127-132, 2005. Google Scholar
  23. Aaron Johnson, Chris Wacek, Rob Jansen, Micah Sherr, and Paul F. Syverson. Users get routed: traffic correlation on tor by realistic adversaries. In Ahmad-Reza Sadeghi, Virgil D. Gligor, and Moti Yung, editors, ACM CCS 2013, pages 337-348. ACM Press, November 2013. URL: https://doi.org/10.1145/2508859.2516651.
  24. Christiane Kuhn, Martin Beck, and Thorsten Strufe. Breaking and (partially) fixing provably secure onion routing. CoRR, abs/1910.13772, 2019. URL: http://arxiv.org/abs/1910.13772.
  25. Albert Kwon, Henry Corrigan-Gibbs, Srinivas Devadas, and Bryan Ford. Atom: Horizontally scaling strong anonymity. In Proceedings of the 26th Symposium on Operating Systems Principles, Shanghai, China, October 28-31, 2017, pages 406-422. ACM, 2017. URL: https://doi.org/10.1145/3132747.3132755.
  26. Michael Mitzenmacher and Eli Upfal. Probability and computing: Randomized algorithms and probabilistic analysis. Cambridge university press, 2005. Google Scholar
  27. Lasse Øverlier and Paul Syverson. Locating hidden servers. In 2006 IEEE Symposium on Security and Privacy, pages 100-114. IEEE Computer Society Press, May 2006. URL: https://doi.org/10.1109/SP.2006.24.
  28. Charles Rackoff and Daniel R. Simon. Cryptographic defense against traffic analysis. In 25th ACM STOC, pages 672-681. ACM Press, May 1993. URL: https://doi.org/10.1145/167088.167260.
  29. Yixin Sun, Anne Edmundson, Laurent Vanbever, Oscar Li, Jennifer Rexford, Mung Chiang, and Prateek Mittal. RAPTOR: Routing Attacks on Privacy in Tor. In USENIX Security Symposium, pages 271-286, 2015. Google Scholar
  30. Nirvan Tyagi, Yossi Gilad, Derek Leung, Matei Zaharia, and Nickolai Zeldovich. Stadium: A distributed metadata-private messaging system. In Proceedings of the 26th Symposium on Operating Systems Principles, Shanghai, China, October 28-31, 2017, pages 423-440. ACM, 2017. URL: https://doi.org/10.1145/3132747.3132783.
  31. Jelle van den Hooff, David Lazar, Matei Zaharia, and Nickolai Zeldovich. Vuvuzela: scalable private messaging resistant to traffic analysis. In Ethan L. Miller and Steven Hand, editors, Proceedings of the 25th Symposium on Operating Systems Principles, SOSP 2015, Monterey, CA, USA, October 4-7, 2015, pages 137-152. ACM, 2015. URL: https://doi.org/10.1145/2815400.2815417.
  32. Ryan Wails, Yixin Sun, Aaron Johnson, Mung Chiang, and Prateek Mittal. Tempest: Temporal dynamics in anonymity systems. PoPETs, 2018(3):22-42, 2018. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact