License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2018.144
URN: urn:nbn:de:0030-drops-91482
Go to the corresponding LIPIcs Volume Portal

Ando, Megumi ; Lysyanskaya, Anna ; Upfal, Eli

Practical and Provably Secure Onion Routing

LIPIcs-ICALP-2018-144.pdf (0.5 MB)


In an onion routing protocol, messages travel through several intermediaries before arriving at their destinations; they are wrapped in layers of encryption (hence they are called "onions"). The goal is to make it hard to establish who sent the message. It is a practical and widespread tool for creating anonymous channels.
For the standard adversary models - passive and active - we present practical and provably secure onion routing protocols. Akin to Tor, in our protocols each party independently chooses the routing paths for his onions. For security parameter lambda, our differentially private solution for the active adversary takes O(log^2 lambda) rounds and requires every participant to transmit O(log^{4} lambda) onions in every round.

BibTeX - Entry

  author =	{Megumi Ando and Anna Lysyanskaya and Eli Upfal},
  title =	{{Practical and Provably Secure Onion Routing}},
  booktitle =	{45th International Colloquium on Automata, Languages, and  Programming (ICALP 2018)},
  pages =	{144:1--144:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-076-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{107},
  editor =	{Ioannis Chatzigiannakis and Christos Kaklamanis and D{\'a}niel Marx and Donald Sannella},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{},
  URN =		{urn:nbn:de:0030-drops-91482},
  doi =		{10.4230/LIPIcs.ICALP.2018.144},
  annote =	{Keywords: Anonymity, traffic analysis, statistical privacy, differential privacy}

Keywords: Anonymity, traffic analysis, statistical privacy, differential privacy
Collection: 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)
Issue Date: 2018
Date of publication: 04.07.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI